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

DOI10.1016/0304-3975(93)90232-IzbMATH Open0787.20035MaRDI QIDQ685449FDOQ685449

Juhani Karhumäki

Publication date: 17 October 1993

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

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

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)

Cites Work

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

Cited In (16)

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

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)