scientific article; zbMATH DE number 3633742

MaRDI QIDQ4194484zbMATH OpenFDO

Authors Arto Salomaa

Publication date 1978

zbMATH Keywords

Context-FreeContext-SensitiveDecidabilityDol Equivalence ProblemEquality SetsFree MonoidLanguagesMorphismsRecursively Enumerable LanguageRegular

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Cited in

(19)

• On binary equality sets and a solution to the test set conjecture in the binary case
• Balance of many-valued transductions and equivalence problems
• Representations of language families by homomorphic equality operations and generalized equality sets
• A representation of recursively enumerable languages by two homomorphisms and a quotient
• Multiple equality sets and Post machines
• 2DST mappings of languages and related problems
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• A note on morphic characterization of languages
• Sticker systems
• Equalizers and kernels in categories of monoids
• Binary equality sets are generated by two words
• Finite transducers and rational transductions
• On some decidability questions concerning supports of rational series
• Unambiguous injective morphisms in free groups
• Ambiguity of morphisms in a free group
• Large Simple Binary Equality Words
• Reachability via cooperating morphisms
• On the difference set of two transductions
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids

This page was built for publication:

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