Alladi Ramakrishnan Hall

Deterministic Suffix-reading Automata

B. Srivathsan

Chennai Mathematical Institute

We present deterministic suffix-reading automata (DSA), a new automaton model over finite words. Our motivation for this model comes from specifications which can be described using rules of the form: "when a certain sequence of inputs is seen, perform this action". DSAs provide a cleaner representation, compared to deterministic finite automata (DFA), in such situations.

Transitions of a DSA are labeled with words. From a state, a DSA triggers an outgoing transition when a word ending with the transition-label is seen. Therefore, rather than moving along an input word letter by letter, a DSA can jump along blocks of letters, with each block ending in a suitable suffix. This feature allows DSAs to recognize regular languages more concisely.

In this talk, we will focus on questions around finding a minimal DSA for a regular language. A key technical ingredient that we will describe is a "natural" method to derive DSAs from a given DFA: a DFA-to-DSA conversion. We make a (surprising) observation that the smallest DSA that we derive from the canonical DFA of a regular language L need not be a minimal DSA for L. This showcases some fundamental bottlenecks (aka. interesting challenges) in determining minimal DSAs. In fact, we prove that given a DFA and a number k, deciding whether there exists a DSA with size less than k is NP-complete.

This is a very fresh model, with plenty of unsolved automata-theoretic and algorithmic questions. We will discuss some of them towards the end of the talk.

Joint work with R Keerthan, R Venkatesh and Sagar Verma.