Reset machines

DOI10.1016/0022-0000(79)90004-7zbMath0427.03029OpenAlexW4210356130MaRDI QIDQ1136756

Ronald V. Book, Sheila A. Greibach, Celia Wrathall

Publication date: 1979

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(79)90004-7

zbMATH Keywords

Turing machinesabstract families of languagesreversal-bounded acceptors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items (19)

Single-tape reset machines ⋮ Fast nondeterministic recognition of context-free languages using two queues ⋮ On the intersection of the class of linear context-free languages and the class of single-reset languages ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On the intersection of stacks and queues ⋮ Characterizations of reduction classes modulo oracle conditions ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Queue Automata: Foundations and Developments ⋮ Multiple equality sets and Post machines ⋮ The equivalence of deterministic gsm replications onQ-rational languages is decidable ⋮ The inclusion of D0L in multi-reset ⋮ QRT FIFO automata, breadth-first grammars and their relations ⋮ On characterisation of language families in terms of inverse morphisms ⋮ Three write heads are as good ask ⋮ On some bounded semiAFLs and AFLs ⋮ Langages à un compteur ⋮ On families of full trios containing counter machine languages ⋮ Partial commutations and faithful rational transductions ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties

Cites Work

• Unnamed Item
• Reversal-bounded multipushdown machines
• Control sets on context-free grammar forms
• One way finite visit automata
• On languages specified by relative acceptance
• Remarks on blind and partially blind one-way multicounter machines
• Principal AFL
• Finite-turn checking automata
• Sur diverses familles de langages fermées par transduction rationnelle
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Simple Representations of Certain Classes of Languages
• Linear Languages and the Intersection Closures of Classes of Languages
• Quasi-realtime languages
• Multitape AFA
• Erasing in context-free AFLs

This page was built for publication: Reset machines