A Purely Homomorphic Characterization of Recursively Enumerable Sets

DOI10.1145/322123.322136zbMath0395.68076OpenAlexW2023198763WikidataQ121821432 ScholiaQ121821432MaRDI QIDQ4178516

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

ComplexityAutomataLanguagesEqualityRecursively Enumerable SetsRegular SetsHomomorphic CharacterizationMinimal SetsPost Correspondence Problem

Mathematics Subject Classification ID

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

Related Items (32)

On morphic generation of regular languages ⋮ Grammars, derivation modes and properties of indexed and type-0 languages ⋮ Yield-languages of two-way pushdown tree automata ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ A representation of recursively enumerable languages by two homomorphisms and a quotient ⋮ Loops in automata and HDTOL relations ⋮ Unnamed Item ⋮ On the equivalence problem for deterministic multitape automata and transducers ⋮ 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 ⋮ Large Simple Binary Equality Words ⋮ The (generalized) Post correspondence problem with lists consisting of two words is decidable ⋮ A note on morphic characterization of languages ⋮ Post correspondence problem: Words possible as primitive solutions ⋮ LARGE SIMPLE BINARY EQUALITY WORDS ⋮ A homomorphic characterization of time and space complexity classes of languages† ⋮ On characterizations of recursively enumerable languages ⋮ 2-testability and relabelings produce everything ⋮ Sticker systems ⋮ Reachability via Cooperating Morphisms ⋮ ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS ⋮ Finite transducers and rational transductions ⋮ ON THE DUAL POST CORRESPONDENCE PROBLEM ⋮ DISTRIBUTED PROCESSING IN AUTOMATA ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Partial commutations and faithful rational transductions ⋮ A homomorphic characterization of recursively enumerable languages ⋮ Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes ⋮ On simplest possible solutions for Post Correspondence Problems

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