A Purely Homomorphic Characterization of Recursively Enumerable Sets

DOI10.1145/322123.322136zbMATH Open0395.68076OpenAlexW2023198763WikidataQ121821432 ScholiaQ121821432MaRDI QIDQ4178516FDOQ4178516

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)

• 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
• On the equivalence problem for deterministic multitape automata and transducers
• Grammars, derivation modes and properties of indexed and type-0 languages
• Representations of language families by homomorphic equality operations and generalized equality sets
• On binary equality sets and a solution to the test set conjecture in the binary case
• Distributed processing in automata
• Test sets and checking words for homomorphism equivalence
• 2-testability and relabelings produce everything
• A representation of recursively enumerable languages by two homomorphisms and a quotient
• Sticker systems
• 2DST mappings of languages and related problems
• A note on morphic characterization of languages
• On characterizations of recursively enumerable languages
• Finite transducers and rational transductions
• On the dual Post correspondence problem
• Post correspondence problem: words possible as primitive solutions
• Multiple equality sets and Post machines
• 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
• Title not available (Why is that?)
• On simplest possible solutions for Post Correspondence Problems
• On morphic generation of regular languages
• Reachability via cooperating morphisms

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)