Restarting Automata with Auxiliary Symbols and Small Lookahead

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publication LATA'11 Proceedings of the 5th international conference on Language and automata theory and applications LATA 2011
Publication date2012
ISBN (Print)978-3-642-21253-6
ISBN (Electronic)978-3-642-21254-3
Publication statusPublished - 2012
SeriesLecture Notes in Computer Science


  • Restarting Automata
  • Lookahead Hierarchies
  • Auxiliary Symbols
  • Context-Free Languages
  • Linear Languages


Dive into the research topics of 'Restarting Automata with Auxiliary Symbols and Small Lookahead'. Together they form a unique fingerprint.

Cite this