Multiple equality sets and Post machines

DOI10.1016/0022-0000(80)90026-4MaRDI QIDQ1148696zbMATH OpenOpenAlexFDO

Authors Franz J. 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

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

Cites work

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

Cited in

(13)

• 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 leftmost derviation in matrix grammars
• Fast nondeterministic recognition of context-free languages using two queues
• On the power of several queues
• On the intersection of stacks and queues
• QRT FIFO automata, breadth-first grammars and their relations
• On some transducer equivalence problems for families of languages
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Uniform simulations of nondeterministic real time multitape turing machines
• Three write heads are as good ask
• Single-tape reset machines
• Queue Automata: Foundations and Developments

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1148696)