The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids

DOI10.1016/0304-3975(84)90004-5zbMath0546.68060OpenAlexW2036991508WikidataQ123024946 ScholiaQ123024946MaRDI QIDQ798007

Juhani Karhumäki

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90004-5

zbMATH Keywords

surveyEhrenfeucht Conjectureequations in free monoidsHDOL sequence equivalence problemslanguages over a binary alphabet

Mathematics Subject Classification ID

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

Related Items

Test sets for finite substitutions, The Ehrenfeucht conjecture: An algebra-framework for its proof, A proof of Ehrenfeucht's conjecture, Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht, The equivalence of finite valued transducers (on HDT0L languages) is decidable, On the size of independent systems of equations in semigroups, Every finitely generated submonoid of a free monoid has a finite Malcev's presentation, Polynomial size test sets for context-free languages, New techniques for proving the decidability of equivalence problem, 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, Unnamed Item, Unnamed Item, On the size of independent systems of equations in semigroups, On test sets for checking morphism equivalence on languages with fair distribution of letters, On three-element codes, On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on intersections of free submonoids of a free monoid
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• On binary equality sets and a solution to the test set conjecture in the binary case
• Sur le théorème du defaut
• Test sets and checking words for homomorphism equivalence
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Equations in free semigroups
• Zeros of Z-rational functions and DOL equivalence
• On the decidability of homomorphism equivalence for languages
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• Checking sets, test sets, rich languages and commutatively closed languages
• The equivalence problem for deterministic TOL-systems is undecidable
• Test sets for context free languages and algebraic systems of equations over a free monoid
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• On the equivalence problem for binary DOL systems
• The decidability of the equivalence problem for DOL-systems
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP