Restarting Automata with Auxiliary Symbols and Small Lookahead

Details Restarting Automata with Auxiliary Symbols and Small Lookahead Restarting Automata with Auxiliary Symbols and Small Lookahead

2011-01-09

arxiv.org/abs/1101.1640v3

Computer Science

Formal Languages and Automata Theory

Full version of the paper accepted to LATA 2011

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Restarting Automata with Auxiliary Symbols and Small Lookahead does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Restarting Automata with Auxiliary Symbols and Small Lookahead, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Restarting Automata with Auxiliary Symbols and Small Lookahead will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-265999