Abstract / Description of output
Determinisation of nondeterministic finite automata is a well-studied problem that plays an important role in compiler theory and system verification. In the latter field, one often encounters automata consisting of millions or even billions of states. On such input, the memory usage of analysis tools becomes the major bottleneck. In this paper we present several determinisation algorithms, all variants of the well-known subset construction, that aim to reduce memory usage and produce smaller output automata. One of them produces automata that are already minimal. We apply our algorithms to determinise automata that describe the possible sequences appearing after a fixed-length run of cellular automaton 110, and obtain a significant improvement in both memory and time efficiency.
Original language | English |
---|---|
Title of host publication | Implementation and Applications of Automata |
Editors | Oscar H. Ibarra, Bala Ravikumar |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer |
Pages | 161-170 |
Number of pages | 10 |
ISBN (Electronic) | 978-3-540-70844-5 |
ISBN (Print) | 978-3-540-70844-5 |
DOIs | |
Publication status | Published - 24 Jul 2008 |
Event | The 13th International Conference on Implementation and Application of Automata, 2008 - San Francisco, United States Duration: 21 Jul 2008 → 24 Jul 2008 Conference number: 13 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Berlin, Heidelberg |
Volume | 5148 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | The 13th International Conference on Implementation and Application of Automata, 2008 |
---|---|
Abbreviated title | CIAA 2008 |
Country/Territory | United States |
City | San Francisco |
Period | 21/07/08 → 24/07/08 |