TY  - JOUR
A1  - Bensch, Suna
A1  - Bordihn, Henning
A1  - Holzer, Markus
A1  - Kutrib, Martin
T1  - On input-revolving deterministic and nondeterministic finite automata
N2  - We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the 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 deterministic 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.
Y1  - 2009
UR  - http://www.sciencedirect.com/science/journal/08905401
U6  - https://doi.org/10.1016/J.Ic.2009.03.002
SN  - 0890-5401
ER  - 
TY  - JOUR
A1  - Bordihn, Henning
A1  - Holzer, Markus
A1  - Kutrib, Martin
T1  - Determination of finite automata accepting subregular languages
N2  - We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, Suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight ill the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown.
Y1  - 2009
UR  - http://www.sciencedirect.com/science/journal/03043975
U6  - https://doi.org/10.1016/j.tcs.2009.05.019
SN  - 0304-3975
ER  -