The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
DOI10.1016/0304-3975(84)90004-5zbMATH Open0546.68060OpenAlexW2036991508WikidataQ123024946 ScholiaQ123024946MaRDI QIDQ798007FDOQ798007
Authors: 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
Recommendations
surveyEhrenfeucht Conjectureequations in free monoidsHDOL sequence equivalence problemslanguages over a binary alphabet
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- Title not available (Why is that?)
- A Purely Homomorphic Characterization of Recursively Enumerable Sets
- 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?)
- Title not available (Why is that?)
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
- Title not available (Why is that?)
- Elementary homomorphisms and a solution of the DOL sequence equivalence problem
- Sur le théorème du defaut
- Title not available (Why is that?)
- On the equivalence problem for binary DOL systems
- The decidability of the equivalence problem for DOL-systems
- On the decidability of homomorphism equivalence for languages
- Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
- Zeros of Z-rational functions and DOL equivalence
- On binary equality sets and a solution to the test set conjecture in the binary case
- Test sets and checking words for homomorphism equivalence
- Equations in free semigroups
- Test sets for context free languages and algebraic systems of equations over a free monoid
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- Title not available (Why is that?)
- A note on intersections of free submonoids of a free monoid
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Checking sets, test sets, rich languages and commutatively closed languages
- The equivalence problem for deterministic TOL-systems is undecidable
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (21)
- On the size of independent systems of equations in semigroups
- Flow Compactifications of Nondiscrete Monoids, Idempotents and Hindman's Theorem
- Efficient constructions of test sets for regular and context-free languages
- Equations over finite sets of words and equivalence problems in automata theory
- 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 three-element codes
- Polynomial size test sets for context-free languages
- Every finitely generated submonoid of a free monoid has a finite Malcev's presentation
- The many facets of string transducers (invited talk)
- A proof of Ehrenfeucht's conjecture
- Multiplicities: A deterministic view of nondeterminism
- On the size of independent systems of equations in semigroups
- The Ehrenfeucht conjecture: An algebra-framework for its proof
- New techniques for proving the decidability of equivalence problem
- Test sets for finite substitutions
- On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages
- On test sets for checking morphism equivalence on languages with fair distribution of letters
- Title not available (Why is that?)
- Title not available (Why is that?)
- The problem of freeness for Euler monoids and Möbius groups
This page was built for publication: The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q798007)
