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

AutomataComplexityEqualityHomomorphic CharacterizationLanguagesMinimal SetsPost Correspondence ProblemRecursively Enumerable SetsRegular Sets

Mathematics Subject Classification ID

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

Cited in

(32)

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

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)