Restarting automata with auxiliary symbols restricted by lookahead size

DSpace Repository

Restarting automata with auxiliary symbols restricted by lookahead size

Overview

Detailed record

dc.contributor.author Schluter, Natalie
dc.date.accessioned 2015-11-30T12:50:17Z
dc.date.available 2015-11-30T12:50:17Z
dc.date.issued 2015
dc.identifier.issn 0020-7160
dc.identifier.uri http://hdl.handle.net/2043/19737
dc.description.abstract This paper presents a study on lookahead hierarchies for restarting automata with auxiliary symbols. We show that the class of languages for deterministic monotone or monotone restarting automaton, whose restart step and rewrite step are separated, coincides with that of the same type of restarting automaton whose restart and rewrite steps are not separated, for any fixed lookahead size. For the non-monotone deterministic case, the lookahead length must be approximately doubled. We then turn our attention to restarting automata with small lookahead. For the general restarting automaton model, we show that there are just two different classes of languages recognized, through the restriction of lookahead size: those with lookahead size 1 and those with lookahead size 2. We also show that the respective (left-) monotone restarting automaton models characterize the context-free languages and that the respective right-left-monotone restarting automata characterize the linear languages both with just lookahead length 2.
dc.format.extent 31
dc.language.iso eng
dc.publisher Taylor & Francis
dc.subject context-free languages
dc.subject lookahead hierarchy
dc.subject lookahead size
dc.subject auxiliary
dc.subject symbols
dc.subject linear languages
dc.subject Church-Rosser
dc.subject restarting automata
dc.subject 68Q05
dc.subject 68Q42
dc.subject 68Q45
dc.subject.classification Sciences
dc.title Restarting automata with auxiliary symbols restricted by lookahead size
dc.type Article, peer reviewed scientific
dc.contributor.department Malmö University. Faculty of Technology and Society
dc.identifier.doi 10.1080/00207160.2014.926005
dc.subject.srsc Research Subject Categories::TECHNOLOGY
dc.relation.ispartofpublication International Journal of Computer Mathematics;5
dc.relation.ispartofpublicationvolume 92
dc.format.ePage 938
dc.format.sPage 908
 Find Full text Files for download

There are no files associated with this item.

This item appears in the following Collection(s)

Overview

Search


Browse

My Account

Statistics