Multiple equality sets and Post machines

DOI10.1016/0022-0000(80)90026-4zbMath0452.68086OpenAlexW2037388662MaRDI QIDQ1148696

Franz-Josef Brandenburg

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90026-4

zbMATH Keywords

homomorphismsrecursively enumerable setsmultiple reset machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Related Items (13)

Single-tape reset machines ⋮ Fast nondeterministic recognition of context-free languages using two queues ⋮ A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers) ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On the intersection of stacks and queues ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Queue Automata: Foundations and Developments ⋮ On some transducer equivalence problems for families of languages ⋮ QRT FIFO automata, breadth-first grammars and their relations ⋮ On the power of several queues ⋮ Three write heads are as good ask ⋮ ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Reset machines
• Reversal-bounded multipushdown machines
• Über einen Automaten mit Pufferspeicherung
• Equality languages and fixed point languages
• Three write heads are as good ask
• Equality Sets and Complexity Classes
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• Unary multiple equality sets: The languages of rational matrices
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Linear Languages and the Intersection Closures of Classes of Languages
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• Quasi-realtime languages
• Some Results on Tape-Bounded Turing Machines
• Multitape AFA

This page was built for publication: Multiple equality sets and Post machines