Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Restarting automata with auxiliary symbols restricted by lookahead size
Malmö högskola, Faculty of Technology and Society (TS).ORCID iD: 0000-0001-8215-4801
2015 (English)In: International Journal of Computer Mathematics, ISSN 0020-7160, E-ISSN 1029-0265, Vol. 92, no 5, p. 908-938Article in journal (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Taylor & Francis, 2015. Vol. 92, no 5, p. 908-938
Keywords [en]
context-free languages, lookahead hierarchy, lookahead size, auxiliary, symbols, linear languages, Church-Rosser, restarting automata, 68Q05, 68Q42, 68Q45
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mau:diva-2501DOI: 10.1080/00207160.2014.926005ISI: 000349117900003Scopus ID: 2-s2.0-84922465785Local ID: 19737OAI: oai:DiVA.org:mau-2501DiVA, id: diva2:1399264
Available from: 2020-02-27 Created: 2020-02-27 Last updated: 2024-02-06Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Schluter, Natalie

Search in DiVA

By author/editor
Schluter, Natalie
By organisation
Faculty of Technology and Society (TS)
In the same journal
International Journal of Computer Mathematics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 53 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf