Systems of equations over a free monoid and Ehrenfeucht's conjecture

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
The decidability of the equivalence problem for DOL-systems
On the decidability of homomorphism equivalence for languages
Simplifications of homomorphisms
The decidability of the dol prefix problem
Test sets and checking words for homomorphism equivalence
Title not available (Why is that?)

Cited In (39)

On the size of independent systems of equations in semigroups
Loops in automata and HDTOL relations
Equations over finite sets of words and equivalence problems in automata theory
The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
On the equivalence problem for deterministic multitape automata and transducers
Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht
Identities and transductions
On binary equality sets and a solution to the test set conjecture in the binary case
Finite degrees of ambiguity in pattern languages
The equivalence of finite valued transducers (on HDT0L languages) is decidable
Systems of word equations, polynomials and linear algebra: a new approach
Compactness of systems of equations in semigroups
On the independence of equations in three variables.
On the defect theorem and simplifiability
One-variable word equations and three-variable constant-free word equations
An optimal bound on the solution sets of one-variable word equations and its consequences
A compactness property of the \(k\)-abelian monoids
Finite transducers and rational transductions
On systems of word equations over three unknowns with at most six occurrences of one of the unknowns
A proof of Ehrenfeucht's conjecture
Multiplicities: A deterministic view of nondeterminism
The descending chain condition on solution sets for systems of equations in groups
On the size of independent systems of equations in semigroups
Multiple constraints on three and four words
An optimal bound on the solution sets of one-variable word equations and its consequences
On maximal chains of systems of word equations
Synchronizable deterministic pushdown automata and the decidability of their equivalence
One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations
The Equivalence Problem of Finite Substitutions on ab*c, with Applications
ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS
Test sets for morphisms with bounded delay
New techniques for proving the decidability of equivalence problem
Title not available (Why is that?)
Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by \(\omega\)
On the equivalence of some transductions involving letter to letter morphisms on regular languages
Inverse morphic equivalence on languages
A note on decidability questions on presentations of word semigroups
On test sets for checking morphism equivalence on languages with fair distribution of letters
The expressibility of languages and relations by word equations

This page was built for publication: Systems of equations over a free monoid and Ehrenfeucht's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786545)