Test sets for finite substitutions

DOI10.1016/0304-3975(86)90171-4zbMath0592.68066OpenAlexW2018277027MaRDI QIDQ1075775

B. George

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90171-4

zbMATH Keywords

free algebraEhrenfeucht conjecturefinitely generated free monoidKönig's Lemma

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

The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ New techniques for proving the decidability of equivalence problem

Cites Work

• Unnamed Item
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• A proof of Ehrenfeucht's conjecture
• The descending chain condition on solution sets for systems of equations in groups
• The Semigroup of Ideals of a Fir is (Usually) Free