Displaying similar documents to “Conversion of regular expressions into realtime automata”

Efficient weighted expressions conversion

Faissal Ouardi, Djelloul Ziadi (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

J. Hromkovic et al. have given an elegant method to convert a regular expression of size n into an ε -free nondeterministic finite automaton having O ( n ) states and O ( n log 2 ( n ) ) transitions. This method has been implemented efficiently in O ( n log 2 ( n ) ) time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in O ( n log 2 ( n ) ) time.

An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid

Laura Giambruno, Antonio Restivo (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumäki on the characterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number...

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some ℓ additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with ℓ nested pebbles....

Note on the complexity of Las Vegas automata problems

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger...

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity: