A Purely Homomorphic Characterization of Recursively Enumerable Sets

DOI10.1145/322123.322136MaRDI QIDQ4178516zbMATH OpenOpenAlexWikidataFDO

Authors Karel II Culik

Publication date 1979

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

Full work available at URL https://doi.org/10.1145/322123.322136

zbMATH Keywords

ComplexityAutomataEqualityLanguagesRecursively Enumerable SetsHomomorphic CharacterizationMinimal SetsPost Correspondence ProblemRegular Sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Recursively (computably) enumerable sets and degrees (03D25)

Cited in

(32)

• Reachability via cooperating morphisms
• Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes
• Loops in automata and HDTOL relations
• Large simple binary equality words
• Partial commutations and faithful rational transductions
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• Grammars, derivation modes and properties of indexed and type-0 languages
• Representations of language families by homomorphic equality operations and generalized equality sets
• On the equivalence problem for deterministic multitape automata and transducers
• On binary equality sets and a solution to the test set conjecture in the binary case
• Test sets and checking words for homomorphism equivalence
• Distributed processing in automata
• 2-testability and relabelings produce everything
• A representation of recursively enumerable languages by two homomorphisms and a quotient
• 2DST mappings of languages and related problems
• A note on morphic characterization of languages
• Sticker systems
• On characterizations of recursively enumerable languages
• Finite transducers and rational transductions
• Multiple equality sets and Post machines
• On the dual Post correspondence problem
• Post correspondence problem: words possible as primitive solutions
• Large Simple Binary Equality Words
• ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS
• A homomorphic characterization of time and space complexity classes of languages†
• A homomorphic characterization of regular languages
• Yield-languages of two-way pushdown tree automata
• A homomorphic characterization of recursively enumerable languages
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• On simplest possible solutions for Post Correspondence Problems
• scientific article; zbMATH DE number 3673546 (Why is no real title available?)
• On morphic generation of regular languages

This page was built for publication: A Purely Homomorphic Characterization of Recursively Enumerable Sets

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