On Switching Finite State Automata
摘要
We introduce the concept of switch transitions for finite state machines. Roughly speaking, a switch transition branches and connects one state (source) with two states (targets), and changes which state it goes to every time it is used. In this way, a switching finite automaton remembers besides the current state also for each switch transition where it points to—this can be seen as an additional bit of memory for each switch transition. We study the accepting capacity of switching automata and show that they are exponentially more succinct than ordinary finite automata. Moreover, the computational complexity of these devices are investigated for standard problems from formal language theory. Here it turns out that some lower bounds can be deduced from problems on regular like expressions with squaring. This is due to the fact that one can construct a linear size switching automaton equivalent to a regular like expression with squaring.