Restarting Automata with Auxiliary Symbols and Small Lookahead

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
Titel LATA'11 Proceedings of the 5th international conference on Language and automata theory and applications LATA 2011
ForlagSpringer
Publikationsdato2012
Sider499-510
ISBN (Trykt)978-3-642-21253-6
ISBN (Elektronisk)978-3-642-21254-3
DOI
StatusUdgivet - 2012
NavnLecture Notes in Computer Science
Vol/bind6638

Fingeraftryk

Dyk ned i forskningsemnerne om 'Restarting Automata with Auxiliary Symbols and Small Lookahead'. Sammen danner de et unikt fingeraftryk.

Citationsformater