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

DOI10.1016/0304-3975(93)90232-IMaRDI QIDQ685449zbMATH OpenFDO

Authors Juhani Karhumäki

Publication date 17 October 1993

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

Full work available at URL https://doi.org/10.1016/0304-3975(93)90232-I

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1047888
• scientific article; zbMATH DE number 3987554
• scientific article; zbMATH DE number 4058892
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3940751 (Why is no real title available?)
• scientific article; zbMATH DE number 4028926 (Why is no real title available?)
• scientific article; zbMATH DE number 4045192 (Why is no real title available?)
• scientific article; zbMATH DE number 4077461 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 50943 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 1988980 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A proof of Ehrenfeucht's conjecture
• Centralizers in Free Associative Algebras
• Codes conjugués
• Codes et motifs
• Equations in free semigroups
• Free Associative Algebras
• On the decidability of homomorphism equivalence for languages
• Sur les rélations rationnelles entre monoides libres
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Test sets for context free languages and algebraic systems of equations over a free monoid
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable
• The decidability of the equivalence problem for DOL-systems
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The equivalence problem of multitape finite automata

Cited in

(16)

• On the existence of prime decompositions
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• Solving language equations using flanked automata
• scientific article; zbMATH DE number 7204548 (Why is no real title available?)
• On the size of independent systems of equations in semigroups
• The descending chain condition on solution sets for systems of equations in groups
• The undecidability of some equivalence problems concerning ngsm's and finite substitutions
• The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
• Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
• The Equivalence Problem of Finite Substitutions on ab*c, with Applications
• Undecidability of the equivalence of finite substitutions on regular language
• The equational theory of regular words
• Band monoid languages revisited
• scientific article; zbMATH DE number 3987554 (Why is no real title available?)
• scientific article; zbMATH DE number 2150281 (Why is no real title available?)
• scientific article; zbMATH DE number 4178784 (Why is no real title available?)

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

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