×
Diekert, Volker; Möbus, Axel

Hotz-isomorhism theorems in formal language theory. (English) Zbl 0665.68059

RAIRO, Inf. Théor. Appl. 23, No. 1, 29-43 (1989).
See the review of the preliminary version of this article [Lect. Notes Comput. Sci. 294, 126-135 (1988; Zbl 0644.68098)].

Cited in 2 Documents

MSC:

68Q45 Formal languages and automata
03D05 Automata and formal grammars in connection with logical questions
20M35 Semigroups in automata theory, linguistics, etc.

Keywords:

equivalence of context-free grammars; Hotz group; Hotz isomorphism; finitely presentable group; Hotz monoids; undecidability

Citations:

Zbl 0635.00015; Zbl 0644.68098
PDF BibTeX XML Cite
\textit{V. Diekert} and \textit{A. Möbus}, RAIRO, Inform. Théor. Appl. 23, No. 1, 29--43 (1989; Zbl 0665.68059)
Full Text: DOI EuDML
  • logo of hbz
  • logo of WorldCat

References:

[1] 1. A. CLIFFORD and G. PRESTON, The Algebraic Theory of Semigroups, Amer. Math. Soc., Vol. I, 1961; Vol. II, 1967. Zbl0111.03403 · Zbl 0111.03403
[2] 2. V. DIEKERT, Investigations on Hotz Groups for Arbitrary grammars, Acta Informatica, Vol. 22, 1986, pp. 679-698. Zbl0612.68067 MR836387 · Zbl 0612.68067
[3] 3. V. DIEKERT, On some variants of the Ehrenfeucht Conjecture, Theoret. Comp. Sci., Vol. 46, 1986, pp. 313-318. Zbl0617.68067 MR869212 · Zbl 0617.68067
[4] 4. C. FROUGNY, J. SAKAROVITCH and E. VALKEMAOn the Hotz Group of a Contextfree Grammar, Acta Informatica, Vol. 18, 1982, pp. 109-115. Zbl0495.68066 MR688347 · Zbl 0495.68066
[5] 5. G. HOTZ, Eine neue Invariante für Kontext-freie Sprachen, Theoret. Comp. Sci, Vol. 11, 1980, pp. 107-116. Zbl0447.68089 MR566697 · Zbl 0447.68089
[6] 6. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Massachusetts, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[7] 7. M. JANTZEN and M. KUDLEK, Homomorphic Images of Sentential Form Languages Defined by Semi-Thue System, Theoret. Comp. Sci., Vol. 33, 1984, pp. 13-43. Zbl0542.68059 MR774218 · Zbl 0542.68059
[8] 8. A. MÖBUS, On Languages with a Hotz-isomorphism, Manuscript, 1986.
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.