On Restarting Automata with Window Size One
From MaRDI portal
Publication:5200077
DOI10.1007/978-3-642-22600-7_2zbMath1341.68104OpenAlexW2129197943MaRDI QIDQ5200077
Publication date: 29 July 2011
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_2
descriptional complexityrestarting automatonlanguage hierarchycooperating distributed systemstateless device
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Membership for growing context-sensitive grammars is polynomial
- Succinct description of regular languages by weak restarting automata
- Theory of traces
- Intersection and union of regular languages and state complexity
- Growing context-sensitive languages and Church-Rosser languages
- Membership problems for regular and context-free trace languages
- Clearing Restarting Automata
- Globally Deterministic CD-Systems of Stateless R(1)-Automata
- Restarting Automata with Auxiliary Symbols and Small Lookahead
- ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA
- An Automata-Theoretical Characterization of Context-Free Trace Languages
- COOPERATING DISTRIBUTED SYSTEMS OF RESTARTING AUTOMATA
- SHRINKING RESTARTING AUTOMATA
- On Nonforgetting Restarting Automata That Are Deterministic and/or Monotone
- OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
- CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages
- On Lookahead Hierarchies for Monotone and Deterministic Restarting Automata with Auxiliary Symbols (Extended Abstract)
- On the Gap-Complexity of Simple RL-Automata
- ON DETERMINISTIC CD-SYSTEMS OF RESTARTING AUTOMATA
- Church-Rosser Thue systems and formal languages
- The characterization by automata of certain classes of languages in the context sensitive area
- Characterizing the Regular Languages by Nonforgetting Restarting Automata
- Strictly Deterministic CD-Systems of Restarting Automata
This page was built for publication: On Restarting Automata with Window Size One
