A proof of Ehrenfeucht's conjecture
From MaRDI portal
Publication:1082090
DOI10.1016/0304-3975(85)90066-0zbMath0602.68066OpenAlexW1965895990WikidataQ123342920 ScholiaQ123342920MaRDI QIDQ1082090
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90066-0
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (47)
Test sets for finite substitutions ⋮ The Ehrenfeucht conjecture: An algebra-framework for its proof ⋮ Many aspects of defect theorems ⋮ Equations in the Partial Semigroup of Words with Overlapping Products ⋮ 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 systems of word equations with simple loop sets ⋮ Equations over the \(k\)-binomial monoids ⋮ On the size of independent systems of equations in semigroups ⋮ Test sets for languages of infinite words ⋮ The expressibility of languages and relations by word equations ⋮ 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 ⋮ Polynomial size test sets for context-free languages ⋮ On the Solution Sets of Entire Systems of Word Equations ⋮ D0L sequence equivalence is inPfor fixed alphabets ⋮ New techniques for proving the decidability of equivalence problem ⋮ On the system of word equations \(x_{0} u^{i}_{1} x_{1} u^{i}_{2} x_{2} u^{i}_{3} x_{3}=y_{0} v^{i}_{1} y_{1} v^{i}_{2} y_{2} v^{i}_{3} y_{3}\) \((i=0,1,2,\ldots)\) in a free monoid ⋮ An Analysis and a Reproof of Hmelevskii’s Theorem ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ Polynomial size test sets for commutative languages ⋮ Compactness of systems of equations in semigroups ⋮ Multiplicities: A deterministic view of nondeterminism ⋮ Efficient constructions of test sets for regular and context-free languages ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ Explicit test sets for iterated morphisms in free monoids and metabelian groups ⋮ One-Variable Word Equations and Three-Variable Constant-Free Word Equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A remark on the representation of trace monoids ⋮ Local and global cyclicity in free semigroups ⋮ Solving word equations ⋮ On maximal chains of systems of word equations ⋮ One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations ⋮ On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations ⋮ On some variants of the Ehrenfeucht conjecture ⋮ 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 ⋮ Algebraic properties of word equations ⋮ Multiple factorizations of words and defect effect ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences ⋮ Linear size test sets for certain commutative languages
Cites Work
- Unnamed Item
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
- Test sets and checking words for homomorphism equivalence
- Groups with free 2-generator subsemigroups
- The descending chain condition on solution sets for systems of equations in groups
- Finiteness Conditions for Soluble Groups
This page was built for publication: A proof of Ehrenfeucht's conjecture
