On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
From MaRDI portal
Publication:2914714
DOI10.1007/978-3-642-31606-7_22zbMATH Open1297.68149OpenAlexW40619283MaRDI QIDQ2914714FDOQ2914714
Authors: Martin Kutrib, Friedrich Otto 
Publication date: 20 September 2012
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31606-7_22
Recommendations
- On the descriptional complexity of the window size for deleting restarting automata
- On the descriptional complexity of deterministic ordered restarting automata
- On shrinking restarting automata of window size one and two
- On restarting automata with window size one
- On the descriptional complexity of stateless deterministic ordered restarting automata
- On restarting automata with auxiliary symbols and small window size
- On deleting deterministic restarting automata that have two windows
- Non-recursive trade-offs for deterministic restarting automata
- Deleting deterministic restarting automata with two windows
- On determinism versus nondeterminism for restarting automata
Cites Work
- On stateless two-pushdown automata and restarting automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Restarting automata
- Regularity and Related Problems for Deterministic Pushdown Automata
- Recursive unsolvability of a problem of Thue
- A regularity test for pushdown machines
- Descriptional complexity -- an introductory survey
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- On Goedel speed-up and succinctness of language representations
- On stateless deterministic restarting automata
- Succinct description of regular languages by weak restarting automata
- Complexity of certain decision problems about congruential languages
- Non-recursive trade-offs for deterministic restarting automata
- ON THE POWER OF RRWW-AUTOMATA
- When Church-Rosser becomes context free
- OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
- Restarting Automata with Auxiliary Symbols and Small Lookahead
Cited In (6)
- On restarting automata with auxiliary symbols and small window size
- On restarting automata with window size one
- On deleting deterministic restarting automata that have two windows
- Non-recursive trade-offs for deterministic restarting automata
- On the descriptional complexity of the window size for deleting restarting automata
- Deleting deterministic restarting automata with two windows
This page was built for publication: On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914714)
