T. V. Griffiths
Abstract
It is shown that the equivalence problem for A-free nondeterministic generalized machines is unsolvable, and it is observed that this result implies the unsolvability of the equality problem for c-finite languages.
- 1 GINSBURG, S. The Mathematical Theory of Conte:ct-Free, Languages. McGraw-Hill, New York, 1966. Google Scholar
- 2 PosT, E. A variant of a recursively unsolvale problem. Bull. A,mer. Math. Soc. 52 (1946), 64-268.Google Scholar
Index Terms
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
Recommendations
Deterministic versus nondeterministic space in terms of synchronized alternating machines
The study of synchronized alternating machines has enabled to characterize several natural complexity classes. It is known that synchronized alternating space SASPACE(S(n))= c>0NSPACE(ncS(n)) for any (space-constructible) function S(n) Hromkovic et al. (...
Nondeterministic state complexity of star-free languages
We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. ...
Nondeterministic fuzzy automata
To handle fuzzy uncertainty in system modeling, nondeterministic finite automata have been generalized into fuzzy automata. After a reexamination of the notions of fuzzy automata in the literature, we ascertain that the fundamental property-...
Comments