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)




Related Items (39)

A proof of Ehrenfeucht's conjectureThe descending chain condition on solution sets for systems of equations in groupsSystèmes entiers d'équations sur un alphabet fini et conjecture d'EhrenfeuchtOn the defect theorem and simplifiabilityThe equivalence of finite valued transducers (on HDT0L languages) is decidableSystems of word equations, polynomials and linear algebra: a new approachOn the size of independent systems of equations in semigroupsThe expressibility of languages and relations by word equationsLoops in automata and HDTOL relationsUnnamed ItemOn the equivalence problem for deterministic multitape automata and transducersA note on decidability questions on presentations of word semigroupsON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNSA compactness property of the \(k\)-abelian monoidsIdentities and transductionsNew techniques for proving the decidability of equivalence problemOn the independence of equations in three variables.The Equivalence Problem of Finite Substitutions on ab*c, with ApplicationsFinite degrees of ambiguity in pattern languagesCompactness of systems of equations in semigroupsMultiplicities: A deterministic view of nondeterminismMultiple constraints on three and four wordsEquations over finite sets of words and equivalence problems in automata theoryOn systems of word equations over three unknowns with at most six occurrences of one of the unknownsOne-Variable Word Equations and Three-Variable Constant-Free Word EquationsOn maximal chains of systems of word equationsOne-Unknown Word Equations and Three-Unknown Constant-Free Word EquationsSynchronizable deterministic pushdown automata and the decidability of their equivalenceOn the size of independent systems of equations in semigroupsFinite transducers and rational transductionsTest 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 ConsequencesOn binary equality sets and a solution to the test set conjecture in the binary caseOn the equivalence of some transductions involving letter to letter morphisms on regular languagesThe Ehrenfeucht conjecture: A compactness claim for finitely generated free monoidsInverse morphic equivalence on languagesOn test sets for checking morphism equivalence on languages with fair distribution of lettersTest sets for morphisms with bounded delayAn Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences




Cites Work




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