DOI

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 languageEnglish
Title of host publicationImplementation and Application of Automata, 7th International Conference, CIAA 2002, Tours, France, July 3-5, 2002, Revised Papers
EditorsJean-Marc Champarnaud, Denis Maurel
Pages169-181
Number of pages13
Volume2608
DOIs
StatePublished - 2003
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
ISSN (Print)0302-9743

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78926284