scientific article; zbMATH DE number 4028926
From MaRDI portal
Publication:3769982
[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.
Recommendations
Cited in
(17)- Prefix and equality languages of rational functions are co-context-free
- Multiplicities: A deterministic view of nondeterminism
- On the size of independent systems of equations in semigroups
- Flatwords and Post Correspondence Problem
- Modern aspects of complexity within formal languages
- scientific article; zbMATH DE number 3868642 (Why is no real title available?)
- Elementariness of a finite set of words is co-NP-complete
- Large Simple Binary Equality Words
- scientific article; zbMATH DE number 4037247 (Why is no real title available?)
- scientific article; zbMATH DE number 4039335 (Why is no real title available?)
- scientific article; zbMATH DE number 4090810 (Why is no real title available?)
- On the size of independent systems of equations in semigroups
- Polynomial size test sets for context-free languages
- Efficient constructions of test sets for regular and context-free languages
- Equations over finite sets of words and equivalence problems in automata theory
- The equivalence problem of multitape finite automata
- New techniques for proving the decidability of equivalence problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769982)