id:"swepub:oai:DiVA.org:umu-31785"
Search: id:"swepub:oai:DiVA.org:umu-31785" > On input-revolving ...
- 1 of 1
- Previous record
- Next record
- To hitlist
On input-revolving deterministic and nondeterministic finite automata
-
- Bensch, Suna (author)
- Umeå universitet,Institutionen för datavetenskap
-
- Bordihn, Henning (author)
- Institut für Informatik, Universität Potsdam
-
- Holzer, Markus (author)
- Institut für Informatik, Universität Giessen
- show more...
- show less...
- (creator_code:org_t)
- 2009
- 2009
- English.
- In: Information and Computation. - 0890-5401 .- 1090-2651. ; 207, s. 1140-1155
- Journal article (peer-reviewed)
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Extended finite automata
- Formal language operations
- Computational power
- Closure properties
- Anti-abstract family of languages
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
- Information and Computation (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Bensch, Suna
- Bordihn, Henning
- Holzer, Markus
- Kutrib, Martin
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Information and ...
- By the university
- Umeå University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
