On characterizations of recursively enumerable languages

DOI10.1007/BF01237236zbMath0686.68060MaRDI QIDQ1262786

Michel Latteux, Paavo Turakainen

Publication date: 1990

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

morphism; grammar; recursively enumerable language

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Iteration of rational transductions, A Kleene characterization of computability, On representing recursively enumerable languages by internal contextual languages, Undecidability of existential properties in picture languages, Middle quotients of linear languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The family of one-counter languages is closed under quotient
• A representation of recursively enumerable languages by two homomorphisms and a quotient
• Bifaithful starry transductions
• Monadic Thue systems
• Reversal-bounded multipushdown machines
• On inverse deterministic pushdown transductions
• Sur le monoide syntactique de \(L^*\)lorsque L est un langage fini
• A note on dpda transductions of {0,1}^∗and inverse dpda transductions of the dyck set
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• How to Make Arbitrary Grammars Look Like Context-Free Grammars
• A Purely Homomorphic Characterization of Recursively Enumerable Sets