Piecewise Directable Automata
Tatjana Radjenovic Petkovic, Magnus Steinby · 2001
In this paper a new strong form of directability of automata is studied. A word $w$ is piecewise directing if any input word containing $w$ as a piecewise subword takes the automaton to the same state from every state. The piecewise directable automata form a variety of automata situated between the varieties of definite automata and directable automata. We describe the sets of piecewise directing words of automata in terms of Haines' embedding order, study the structure of piecewise directable automata, and present criteria for an automaton to be piecewise directable. We also consider the congruences of an automaton which yield a piecewise directable quotient automaton and show that any $n$-state piecewise directable automaton has a piecewise directing word of length ${}\leq \binom{n}{k}$.