Reset machines

DOI10.1016/0022-0000(79)90004-7MaRDI QIDQ1136756zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3483582 (Why is no real title available?)
• Control sets on context-free grammar forms
• Erasing in context-free AFLs
• Finite-turn checking automata
• Linear Languages and the Intersection Closures of Classes of Languages
• Multitape AFA
• On languages specified by relative acceptance
• One way finite visit automata
• Principal AFL
• Quasi-realtime languages
• Remarks on blind and partially blind one-way multicounter machines
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Reversal-bounded multipushdown machines
• Simple Representations of Certain Classes of Languages
• Sur diverses familles de langages fermées par transduction rationnelle

Cited in

(19)

• Partial commutations and faithful rational transductions
• 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 characterisation of language families in terms of inverse morphisms
• Fast nondeterministic recognition of context-free languages using two queues
• On families of full trios containing counter machine languages
• On the intersection of stacks and queues
• The inclusion of D0L in multi-reset
• Multiple equality sets and Post machines
• QRT FIFO automata, breadth-first grammars and their relations
• 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
• On some bounded semiAFLs and AFLs
• The equivalence of deterministic gsm replications onQ-rational languages is decidable
• Characterizations of reduction classes modulo oracle conditions
• Single-tape reset machines
• Queue Automata: Foundations and Developments
• Langages à un compteur

This page was built for publication: Reset machines

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