Equality Sets and Complexity Classes
Authors:
- Ronald V. BookRBRonald V. Book
- Franz–Josef BrandenburgFBFranz–Josef Brandenburg
- 1 November 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 9 (4) , 729-743
Abstract
If $h_1 $, $h_2 $ are two homomorphisms, then the equality set$\operatorname{Eq}(h_1 ,h_2 )$ of $h_1 $, $h_2 $ is $\operatorname{Eq} (h_1 ,h_2 ) = \{ w | h_1 (w) = h_2 (w)\} $. In this paper it is shown how to characterize complexity classes of formal languages in terms of equality sets of pairs of homomorphisms with bounded balance. In addition the complete twin shuffle language is investigated, and it is shown that for alphabets with at least two letters, this language cannot be represented as the equality set of a pair of homomorphisms unless both homomorphisms are erasing and have linear bounded balance.
Keywords
This publication has 10 references indexed in Scilit:
- Multiple equality sets and post machinesJournal of Computer and System Sciences, 1980
- Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable LanguagesJournal of the ACM, 1980
- Polynomial Space and Transitive ClosureSIAM Journal on Computing, 1979
- A Purely Homomorphic Characterization of Recursively Enumerable SetsJournal of the ACM, 1979
- On simple representations of language familiesRAIRO. Informatique théorique, 1979
- On the homomorphic characterizations of families of languagesLecture Notes in Computer Science, 1979
- On the decidability of homomorphism equivalence for languagesJournal of Computer and System Sciences, 1978
- Hierarchies of memory limited computations1965
- The equation $a^M=b^Nc^P$ in a free group.The Michigan Mathematical Journal, 1962
- Theory of Formal Systems. (AM-47)1961