13:00
14:00

[MTV] B Srivathsan (CMI) - Deterministic Suffix-reading Automata

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 the talk, we will describe a procedure to construct a minimal DSA for a regular language, starting from its minimal DFA.

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

salle 178, zoom: https://bordeaux-inp-fr.zoom.us/j/89508306159