Sökning: id:"swepub:oai:DiVA.org:umu-31785" >
On input-revolving ...
-
Bensch, SunaUmeå universitet,Institutionen för datavetenskap
(författare)
On input-revolving deterministic and nondeterministic finite automata
- Artikel/kapitelEngelska2009
Förlag, utgivningsår, omfång ...
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:umu-31785
-
https://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-31785URI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:art swepub-publicationtype
Anmärkningar
-
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.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Bordihn, HenningInstitut für Informatik, Universität Potsdam
(författare)
-
Holzer, MarkusInstitut für Informatik, Universität Giessen
(författare)
-
Kutrib, MartinInstitut für Informatik, Universität Giessen
(författare)
-
Umeå universitetInstitutionen för datavetenskap
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:Information and Computation207, s. 1140-11550890-54011090-2651
Internetlänk
Hitta via bibliotek
Till lärosätets databas