On binary equality sets and a solution to the test set conjecture in the binary case

DOI10.1016/0021-8693(83)90119-9zbMath0523.68066OpenAlexW2043837664WikidataQ122958005 ScholiaQ122958005MaRDI QIDQ1056551

Juhani Karhumäki, Grzegorz Rozenberg, Andrzej Ehrenfeucht

Publication date: 1983

Published in: Journal of Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0021-8693(83)90119-9

zbMATH Keywords

equality setbinary alphabetinjective morphismstest set conjecture

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 (14)

Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht ⋮ On the subword equivalence problem for morphic words ⋮ Large Simple Binary Equality Words ⋮ Efficient constructions of test sets for regular and context-free languages ⋮ Binary equality words with two $b$'s ⋮ A note on intersections of free submonoids of a free monoid ⋮ The intersection of \(3\)-maximal submonoids ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Inverse morphic equivalence on languages ⋮ On test sets for checking morphism equivalence on languages with fair distribution of letters ⋮ On cancellation properties of languages which are supports of rational power series ⋮ Test sets for morphisms with bounded delay ⋮ Binary equality sets are generated by two words ⋮ Linear size test sets for certain commutative languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• Test sets and checking words for homomorphism equivalence
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Test sets for context free languages and algebraic systems of equations over a free monoid
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• The decidability of the equivalence problem for DOL-systems
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A variant of a recursively unsolvable problem

This page was built for publication: On binary equality sets and a solution to the test set conjecture in the binary case