This paper studies practical algorithms for dealing with a particular family of cellular automata, which has recently been proved computationally equivalent to linear conjunctive grammars. The relation between these grammars and these automata resembles that between regular expressions and finite automata: while the former are better suited for human use, the latter are considerably easier to implement. In this paper, an algorithm for converting an arbitrary linear conjunctive gram-mar to an equivalent automaton is proposed, and different techniques of reducing the size of existing automata are studied.
Original language | English |
---|---|
Title of host publication | Implementation and Application of Automata, 7th International Conference, CIAA 2002, Tours, France, July 3-5, 2002, Revised Papers |
Editors | Jean-Marc Champarnaud, Denis Maurel |
Pages | 169-181 |
Number of pages | 13 |
Volume | 2608 |
DOIs | |
State | Published - 2003 |
Externally published | Yes |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Publisher | Springer Nature |
ISSN (Print) | 0302-9743 |
ID: 78926284