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




Related Items (36)

On Boolean closed full trios and rational Kripke framesOn morphic generation of regular languagesPARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMSAmbiguity of Morphisms in a Free GroupOn the generating power of regularly controlled bidirectional grammarsOn stateless multihead automata: hierarchies and the emptiness problemOn purely morphic characterizations of context-free languagesRepresentations of language families by homomorphic equality operations and generalized equality setsA representation of recursively enumerable languages by two homomorphisms and a quotientUnnamed ItemPrefix and equality languages of rational functions are co-context-freeSome wonders of a bio-computer-scientistMultiple equality sets and Post machinesComputational power of two stacks with restricted communicationThe (generalized) Post correspondence problem with lists consisting of two words is decidableRefining the hierarchy of blind multicounter languages and twist-closed trios.A note on morphic characterization of languagesComplete symmetry in d2l systems and cellular automataOn some transducer equivalence problems for families of languagesCharacterizations of re languages starting from internal contextual languagesOn characterisation of language families in terms of inverse morphismsLook-ahead on pushdownsOn characterizations of recursively enumerable languagesSticker systemsReachability via Cooperating MorphismsON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMSFixed point languages of rational transductionsFinite transducers and rational transductionsON THE LEFTMOST DERVIATION IN MATRIX GRAMMARSOn binary equality sets and a solution to the test set conjecture in the binary caseTopics in the theory of DNA computing.The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoidsAn inverse homomorphic characterization of full principal AFLPartial commutations and faithful rational transductionsA homomorphic characterization of recursively enumerable languagesUnambiguous injective morphisms in free groups




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