Equations over finite sets of words and equivalence problems in automata theory

DOI10.1016/0304-3975(93)90232-IzbMath0787.20035MaRDI QIDQ685449

Juhani Karhumäki

Publication date: 17 October 1993

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

zbMATH Keywords

free monoidsystem of equationsEhrenfeucht conjecturefinite sets of wordsfinite subsystemmonoid of finite multisetsmonoid of prefix codes

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (5)

Undecidability of the equivalence of finite substitutions on regular language ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ On the existence of prime decompositions ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ The undecidability of some equivalence problems concerning ngsm's and finite substitutions

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
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• The equivalence problem of multitape finite automata
• A proof of Ehrenfeucht's conjecture
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Equations in free semigroups
• Sur les rélations rationnelles entre monoides libres
• On the decidability of homomorphism equivalence for languages
• Codes et motifs
• Test sets for context free languages and algebraic systems of equations over a free monoid
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The decidability of the equivalence problem for DOL-systems
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Free Associative Algebras
• Centralizers in Free Associative Algebras
• Codes conjugués

This page was built for publication: Equations over finite sets of words and equivalence problems in automata theory