Representations of language families by homomorphic equality operations and generalized equality sets
From MaRDI portal
Publication:1099633
DOI10.1016/0304-3975(87)90103-4zbMath0638.68069OpenAlexW2035012445WikidataQ122631081 ScholiaQ122631081MaRDI QIDQ1099633
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(87)90103-4
formal languagerecursively enumerable setsregular setsgeneralized equality setshomomorphic equalitiesPreset machines
Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Turing machines and related notions (03D10)
Related Items (2)
Some Characterization of Recursively Enumerable Sets ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Syntactic operators on full semiAFLs
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Inverse morphic equivalence on languages
- A morphic representation of EOL languages and other ETOL languages
- Cônes rationnels commutatifs
- Reset machines
- Multiple equality sets and Post machines
- A homomorphic characterization of regular languages
- A note on Post's correspondence problem
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- A note on morphic characterization of languages
- Reversal-bounded multipushdown machines
- Control sets on context-free grammar forms
- One way finite visit automata
- On languages specified by relative acceptance
- Hierarchy theorems for two-way finite state transducers
- Elementary homomorphisms and a solution of the DOL sequence equivalence problem
- A homomorphic characterization of principal semi AFLs without using intersection with regular sets
- Checking automata and one-way stack languages
- AFL with the semilinear property
- Equality languages and fixed point languages
- Three write heads are as good ask
- A homomorphic characterization of time and space complexity classes of languages†
- Equality Sets and Complexity Classes
- Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
- A Morphic Representation of Complements of Recursively Enumerable Sets
- Unary multiple equality sets: The languages of rational matrices
- Reversal-Bounded Acceptors and Intersections of Linear Languages
- Simple Representations of Certain Classes of Languages
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- The decidability of the equivalence problem for DOL-systems
- Linear Languages and the Intersection Closures of Classes of Languages
- Rudimentary Predicates and Relative Computation
- Visits, crosses, and reversals for nondeterministic off-line machines
- A Purely Homomorphic Characterization of Recursively Enumerable Sets
- Quasi-realtime languages
- On the closure of AFL under reversal
- Multitape AFA
- Erasing in context-free AFLs
This page was built for publication: Representations of language families by homomorphic equality operations and generalized equality sets
