Reset sequences for monotonic automata. (English) Zbl 0698.68058

Summary: Natarajan reduced the problem of designing a certain type of mechanical parts orienter to that of finding reset sequences for monotonic deterministic finite automata. He gave algorithms that in polynomial time either find such sequences or prove that no such sequence exists. A new algorithm based on breadth-first search is presented that runs in faster asymptotic time than Natarajan’s algorithms, and in addition finds the shortest possible reset sequence if such a sequence exists. Tight bounds on the length of the minimum reset sequence are given. The time and space bounds of another algorithm given by Natarajan are further improved. That algorithm finds reset sequences for arbitrary deterministic finite automata when all states are initially possible.


68Q45 Formal languages and automata
68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI