On the Hotz group of a context-free grammar. (English) Zbl 0495.68066


68Q45 Formal languages and automata
Full Text: DOI


[1] Anisimov, A.V., Seifert, F.D.: Zur algebraischen Charakteristik der durch kontextfreie Sprachen definierten Gruppen. Elektronische Informationsverarbeitung und Kybernetik11, 695-702 (1975) · Zbl 0322.68047
[2] Boasson, L.: Dérivations et réductions dans les grammaires algébriques. In: Proc. of the 7th I.C.A.L.P., Lecture Notes in Computer Science85, 109-118 (1980)
[3] Clifford, A., Preston, G.: The algebraic theory of semigroups. Amer. Math. Soc., Vol.1 (1961), Vol.2 (1967) · Zbl 0111.03403
[4] Frougny, Ch.: Simple deterministic NTS languages. Information Processing Letters12 (4), 174-178 (1981) · Zbl 0482.68067 · doi:10.1016/0020-0190(81)90094-6
[5] Harrison, M.: Introduction to Formal Language Theory. Addison Wesley 1978 · Zbl 0411.68058
[6] Hotz, G.: Eine neue Invariante für kontexfreie Sprachen. Theoret. Computer Sci.11, 107-116 (1980) · Zbl 0447.68089 · doi:10.1016/0304-3975(80)90040-7
[7] Hotz, G.: Über die Darstellbarkeit des syntaktischen Monoides kontextfreier Sprachen. R.A.I.R.O. Informatique théorique13, 337-345 (1979) · Zbl 0428.68085
[8] Lang, S.: Algebra. Addison Wesley 1965
[9] Muller, D.E., Schupp, P.E.: Pushdown automata, graphs, ends, second-order logic, and reachability problems. In: Proc. of the 13th symposium on Theory of Computing, 46-54 (1981)
[10] Sakarovitch, J.: Syntaxe des langages de Chomsky. Th. Sci. Math., Univ. Paris VII, Paris 1979
[11] Senizergues, G.: Décidabilité de l’équivalence des grammaires N.T.S. Thèse 3ème cycle Math., Univ. Paris VII, Paris 1981 · Zbl 0482.68066
[12] Valkema, E.: Einige Zusammenhänge zwischen Halbgruppen und formale Sprachen. Diplomarbeit, Kiel 1970
[13] Valkema, E.: On some relations between formal languages and groups. In: Proc. of ?Categorical and Algebraic Methods in Computer Science and System Theory?, Univ. Dortmund, 116-123 (1978)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.