ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA

DOI10.1142/S0129054110007556zbMath1207.68193MaRDI QIDQ3056279

Hartmut Messerschmidt, Friedrich Otto, Martin Kutrib

Publication date: 11 November 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

restarting automatonstateless devicetwo-pushdown automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Weighted restarting automata and pushdown relations ⋮ On CD-Systems of Stateless Deterministic Two-Phase RR(1)-Automata ⋮ On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata ⋮ Automata with Modulo Counters and Nondeterministic Counter Bounds ⋮ Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata ⋮ Hierarchies and Characterizations of Stateless Multicounter Machines ⋮ On stateless deterministic restarting automata ⋮ Reversible Limited Automata ⋮ Weighted Restarting Automata and Pushdown Relations ⋮ On CD-systems of stateless deterministic R-automata with window size one ⋮ Head and state hierarchies for unary multi-head finite automata ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA ⋮ On Stateless Multicounter Machines ⋮ Stateless multicounter \(5'\to 3'\) Watson-Crick automata: the deterministic case ⋮ On decision problems for parameterized machines ⋮ On Stateless Deterministic Restarting Automata ⋮ On Restarting Automata with Window Size One ⋮ An Automata-Theoretical Characterization of Context-Free Trace Languages ⋮ CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store ⋮ STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES ⋮ Globally deterministic CD-systems of stateless R-automata with window size 1 ⋮ A NOTE ON LIMITED PUSHDOWN ALPHABETS IN STATELESS DETERMINISTIC PUSHDOWN AUTOMATA ⋮ Unnamed Item

Uses Software

• UCFL

Cites Work

• Unnamed Item
• Growing context-sensitive languages and Church-Rosser languages
• Computing with membranes
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Lower bound technique for length-reducing automata
• Locally testable languages
• Algebraic decision procedures for local testability