Systems of equations over a free monoid and Ehrenfeucht's conjecture
From MaRDI portal
Publication:786545
DOI10.1016/0012-365X(83)90152-8zbMath0528.68057WikidataQ123240216 ScholiaQ123240216MaRDI QIDQ786545
Juhani Karhumäki, Karel II Culik
Publication date: 1983
Published in: Discrete Mathematics (Search for Journal in Brave)
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Grammars and rewriting systems (68Q42)
Related Items (39)
A proof of Ehrenfeucht's conjecture ⋮ The descending chain condition on solution sets for systems of equations in groups ⋮ Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht ⋮ On the defect theorem and simplifiability ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Systems of word equations, polynomials and linear algebra: a new approach ⋮ On the size of independent systems of equations in semigroups ⋮ The expressibility of languages and relations by word equations ⋮ Loops in automata and HDTOL relations ⋮ Unnamed Item ⋮ On the equivalence problem for deterministic multitape automata and transducers ⋮ A note on decidability questions on presentations of word semigroups ⋮ ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS ⋮ A compactness property of the \(k\)-abelian monoids ⋮ Identities and transductions ⋮ New techniques for proving the decidability of equivalence problem ⋮ On the independence of equations in three variables. ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ Finite degrees of ambiguity in pattern languages ⋮ Compactness of systems of equations in semigroups ⋮ Multiplicities: A deterministic view of nondeterminism ⋮ Multiple constraints on three and four words ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ One-Variable Word Equations and Three-Variable Constant-Free Word Equations ⋮ On maximal chains of systems of word equations ⋮ One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ On the size of independent systems of equations in semigroups ⋮ Finite transducers and rational transductions ⋮ Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by \(\omega\) ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Inverse morphic equivalence on languages ⋮ On test sets for checking morphism equivalence on languages with fair distribution of letters ⋮ Test sets for morphisms with bounded delay ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Test sets and checking words for homomorphism equivalence
- On the decidability of homomorphism equivalence for languages
- The decidability of the dol prefix problem
- The decidability of the equivalence problem for DOL-systems
- Simplifications of homomorphisms
This page was built for publication: Systems of equations over a free monoid and Ehrenfeucht's conjecture
