zbMATH — the first resource for mathematics

On recent trends in formal language theory. (English) Zbl 0632.68070
Automata, languages and programming, Proc. 14th Int. Colloq., Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 267, 136-162 (1987).
[For the entire collection see Zbl 0616.00013.]
This is a survey of the impact of the D0L sequence equivalence problem on formal language theory; it does not contain any new results. Special attention is given to the following areas: Equality languages and representation of families of languages and transducers; the Post correspondence problem; the Ehrenfeucht conjecture; equivalence of mappings on languages. Some new problems are formulated, and an extensive bibliography is appended.
Reviewer: M.Armbrust

68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science
20M35 Semigroups in automata theory, linguistics, etc.
03D05 Automata and formal grammars in connection with logical questions