umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On input-revolving deterministic and nondeterministic finite automata
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Institut für Informatik, Universität Potsdam.
Institut für Informatik, Universität Giessen.
Institut für Informatik, Universität Giessen.
2009 (Engelska)Ingår i: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 207, s. 1140-1155Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any determinstic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.

Ort, förlag, år, upplaga, sidor
2009. Vol. 207, s. 1140-1155
Nyckelord [en]
Extended finite automata, Formal language operations, Computational power, Closure properties, Anti-abstract family of languages
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-31785OAI: oai:DiVA.org:umu-31785DiVA, id: diva2:294226
Tillgänglig från: 2010-02-16 Skapad: 2010-02-16 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Bensch, Suna

Sök vidare i DiVA

Av författaren/redaktören
Bensch, Suna
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Information and Computation
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 507 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf