On characterizations of recursively enumerable languages. (English) Zbl 0686.68060

V. Geffert [Theor. Comput. Sci. 62, 235-249 (1988; Zbl 0664.68075)] has shown that each recursively enumerable language L over \(\Sigma\) can be expressed in the form \(L=\{h(x)^{-1}g(x)|\) x in \(\Delta^+\}\cap \Sigma^*\) where \(\Delta\) is an alphabet and g, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert’s result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations of L. For instance, \(L=\rho (L_ 0)\cap \Sigma^*\) where \(L_ 0\) is a minimal linear language and \(\rho\) is the Dyck reduction \(a\bar a\to \epsilon\), \(A\bar A\to \epsilon\).
Reviewer: M.Latteux


68Q45 Formal languages and automata


Zbl 0664.68075
Full Text: DOI


[1] Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci.8, 315-332 (1974) · Zbl 0309.68043
[2] Book, R.V., Jantzen, M., Wrathall, C.: Monadic Thue systems. Theor. Comput. Sci.19, 231-251 (1982) · Zbl 0488.03020
[3] Culik, K. II: A purely homomorphic characterization of recursively enumerable sets. J. Assoc. Comput. Math.26, 345-350 (1979) · Zbl 0395.68076
[4] Engelfriet, J., Rozenberg, G.: Fixed point languages, equality languages, and representation of recursively enumerable languages. J. Assoc. Comput. Mach.27, 499-518 (1980) · Zbl 0475.68047
[5] Geffert, V.: A representation of recursively enumerable languages by two homomorphisms and a quotient. Theor. Comput. Sci.62, 235-249 (1988) · Zbl 0664.68075
[6] Geffert, V.: Context-free-like forms for the phrase-structure grammars. (Lect. Notes Comput. Sci., vol. 324, pp. 309-317) Berlin Heidelberg New York: Springer 1988 · Zbl 0652.68095
[7] Latteux, M., Leguy, J.: On composition of morphisms and inverse morphisms. (Lect. Notes Comput. Sci., vol. 154, pp. 420-432) Berlin Heidelberg New York: Springer 1983 · Zbl 0523.68067
[8] Latteux, M., Leguy, J., Ratoandromanana, B.: The family of one-counter languages is closed under quotient. Acta Inf.22, 579-588 (1985) · Zbl 0585.68069
[9] Latteux, M., Timmerman, E.: Bifaithful starry transductions. Inf. Process. Lett.28, 1-4 (1988) · Zbl 0666.68072
[10] Pin, J.E.: Sur le monoide syntactique deL * lorsqueL est un langage fini. Theor. Comput. Sci.7, 211-215 (1978) · Zbl 0388.20050
[11] Salomaa, A.: Formal languages. New York: Academic Press 1973 · Zbl 0262.68025
[12] Salomaa, A.: Jewels of Formal Language Theory. Rockville, Maryland: Computer Sience Press, 1981 · Zbl 0487.68064
[13] Savitch, W.J.: How to make arbitrary grammars look like context-free grammars. SIAM J. Comput.2, 174-182 (1973) · Zbl 0298.68057
[14] Turakainen, P.: On characterization of recursively enumerable languages in terms of linear languages and VW-grammars. Indagationes Math.40, 145-153 (1978) · Zbl 0369.68049
[15] Turakainen, P.: A machine-oriented approach to compositions of morphisms and inverse morphisms. Bull. EATCS20, 162-166 (1983)
[16] Turakainen, P.: Transducers and compositions of morphisms and inverse morphisms. In: Studies in honour of Arto Kustaa Salomaa on the occasion of his fiftieth birthday. Ann. Univ. Turku. Ser. A I186, 118-128 (1984) · Zbl 0541.68045
[17] Vitányi, P.M.B.: A note on DPDA transductions of {0,1}* and inverse DPDA transductions of the Dyck set. Int. J. Comput. Math.9, 131-137 (1981) · Zbl 0454.68098
[18] Vitányi, P.M.B., Savitch, W.J.: On inverse deterministic pushdown transductions. J. Comput. Syst. Sci.16, 423-444 (1978) · Zbl 0376.68051
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.