zbMATH — the first resource for mathematics

A representation of recursively enumerable languages by two homomorphisms and a quotient. (English) Zbl 0664.68075
For two strings x and y, \(x\setminus y\) is the string z when \(y=xz\); otherwise \(x\setminus y\) is undefined. The author proves the following representation theorem: For each recursively enumerable set L (over alphabet \(\Sigma)\) there exist two homomorphisms \(h_ 1\), \(h_ 2:\) \(\Sigma^*_ 1\to \Sigma^*_ 2\) \((\Sigma \subseteq \Sigma_ 2)\) such that for every \(w\in \Sigma^*\), \(w\in L\) if and only if \(w=h_ 1(x)\setminus h_ 2(x)\) for some \(x\in \Sigma^*_ 1.\)
The author discusses some complexity issues related to this representation and also some variants of the representation result.
Reviewer: G.Slutzki

68Q45 Formal languages and automata
Full Text: DOI
[1] Culik, K., A purely homomorphic representation of recursively enumerable sets, J. ACM, 26, 345-350, (1979) · Zbl 0395.68076
[2] Culik, K.; Diamond, N.D., A homomorphic characterization of time and space complexity classes of languages, Internat. J. comput. math., 8, 207-222, (1980) · Zbl 0444.68035
[3] Engelfriet, J.; Rozenberg, G., Fixed point languages, equality languages and representation of recursively enumerable languages, J. ACM, 27, 499-518, (1980) · Zbl 0475.68047
[4] Geffert, V., Grammars with context dependency restricted to synchronization, (), 370-378
[5] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[6] Harrison, M., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[7] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, MA · Zbl 0196.01701
[8] Rovan, B., A framework for study grammars, (), 473-482
[9] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
[10] Salomaa, A., Equality sets of homomorphisms of free monoids, Acta cybernet, 4, 127-139, (1978) · Zbl 0407.68077
[11] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.