Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
From MaRDI portal
Publication:3930659
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
shuffleTuring machinePost correspondence problemrepresentation of languagesAFL generatordeterministic sequential machine
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