Restarting Automata with Auxiliary Symbols and Small Lookahead
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewPublication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 499-510Publication milestones
- Published - 2012
Publication status
Published - 2012
Publisher
Springer, United States, GermanyBook series
- Book series name: Lecture Notes in Computer Science
Volume: 6638
ISSN: 0302-9743
ISBN (Print)
978-3-642-21253-6 ISBN (Electronic)
978-3-642-21254-3Publication IDs
- Scopus: 85038037666
Host publication title
LATA'11 Proceedings of the 5th international conference on Language and automata theory and applications LATA 2011Abstract
We present a study on lookahead hierarchies for restarting automata with auxiliary symbols and small lookahead. In particular, we show that there are just two different classes of languages recognised by RRWW automata, through the restriction of lookahead size. We also show that the respective (left-) monotone restarting automaton models characterise the context-free languages and that the respective right-left-monotone restarting automata characterise the linear languages both with just lookahead length 2.
Publication metrics
PlumX, opens in new tab
Citations
7
Captures
2