| 1. |
- Abdulla, Aziz, et al.
(författare)
-
Monotonic Abstraction : on Efficient Verification of Parameterized Systems
- 2009
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 20:5, s. 779-801
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce the simple and efficient method of monotonic abstraction to prove safety properties for parameterized systems with linear topologies. A process in the system is a finite-state automaton, where the transitions are guarded by both local and global conditions. Processes may communicate via broadcast, rendez-vous and shared variables over finite domains. The method of monotonic abstraction derives an over-approximation of the induced transition system that allows the use of a simple class of regular expressions as a symbolic representation. Compared to traditional regular model checking methods, the analysis does not require the manipulation of transducers, and hence its simplicity and efficiency. We have implemented a prototype that works well on several mutual exclusion algorithms and cache coherence protocols
|
|
| 2. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Bisimulation minimization of tree automata
- 2007
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 18:4, s. 699-713
-
Tidskriftsartikel (refereegranskat)abstract
- We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of $O(\hat{r} m \log n)$, where $\hat{r}$ is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.
|
|
| 3. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Bisimulation minimization of tree automata
- 2007
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 18:4, s. 699-713
-
Tidskriftsartikel (refereegranskat)
|
|
| 4. |
- Abdulla, Parosh Aziz, et al.
(författare)
-
Composed bisimulation for tree automata
- 2009
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 20:4, s. 685-700
-
Tidskriftsartikel (refereegranskat)
|
|
| 5. |
- Dessmark, Anders, et al.
(författare)
-
On the approximability of maximum and minimum edge clique partition problems
- 2007
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 18:2, s. 217-226
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the following clustering problems: given an undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approximations for graph classes for which maximum cliques can be found efficiently.
|
|
