Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages

DOI10.1145/322203.322211zbMath0475.68047OpenAlexW2020651750WikidataQ128705358 ScholiaQ128705358MaRDI QIDQ3930659

Grzegorz Rozenberg, Joost Engelfriet

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/fixed-point-languages-equality-languages-and-representation-of-recursively-enumerable-languages(fd22fac0-bcac-4124-b555-5e70dc1e4fef).html

zbMATH Keywords

shuffle Turing machine Post correspondence problem representation of languages AFL generator deterministic sequential machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (36)

On Boolean closed full trios and rational Kripke frames ⋮ On morphic generation of regular languages ⋮ PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS ⋮ Ambiguity of Morphisms in a Free Group ⋮ On the generating power of regularly controlled bidirectional grammars ⋮ On stateless multihead automata: hierarchies and the emptiness problem ⋮ On purely morphic characterizations of context-free languages ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ A representation of recursively enumerable languages by two homomorphisms and a quotient ⋮ Unnamed Item ⋮ Prefix and equality languages of rational functions are co-context-free ⋮ Some wonders of a bio-computer-scientist ⋮ Multiple equality sets and Post machines ⋮ Computational power of two stacks with restricted communication ⋮ The (generalized) Post correspondence problem with lists consisting of two words is decidable ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ A note on morphic characterization of languages ⋮ Complete symmetry in d2l systems and cellular automata ⋮ On some transducer equivalence problems for families of languages ⋮ Characterizations of re languages starting from internal contextual languages^∗ ⋮ On characterisation of language families in terms of inverse morphisms ⋮ Look-ahead on pushdowns ⋮ On characterizations of recursively enumerable languages ⋮ Sticker systems ⋮ Reachability via Cooperating Morphisms ⋮ ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS ⋮ Fixed point languages of rational transductions ⋮ Finite transducers and rational transductions ⋮ ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ Topics in the theory of DNA computing. ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ An inverse homomorphic characterization of full principal AFL ⋮ Partial commutations and faithful rational transductions ⋮ A homomorphic characterization of recursively enumerable languages ⋮ Unambiguous injective morphisms in free groups

This page was built for publication: Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages