Set-theoretical operations on -multiple languages
Jaroslav Král (1967)
Kybernetika
Similarity:
Displaying similar documents to “A note on Glushkov's algorithm of the synthesis of finite automata”
Set-theoretical operations on -multiple languages
Finite branching automata
Havel, Ivan M. (1974)
Kybernetika
Similarity:
Bounded push down automata
Branislav Rovan (1969)
Kybernetika
Similarity:
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...