CS Faculty Talks Date: Monday, 7 October 2024 Time: 11:00 - 11:50 AM Venue: Seminar Hall Deterministic Suffix-reading Automata B Srivathsan Chennai Mathematical Institute. 07-10-2024 Abstract We present deterministic suffix-reading automata (DSA), a new au- tomaton model over finite words. Our motivation for this model comes from formal 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 end- ing 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. 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.
|