{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T09:14:56Z","timestamp":1778145296120,"version":"3.51.4"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2026,3,12]]},"abstract":"<jats:p>We introduce deterministic suffix-reading automata (DSA), a new automaton model over finite words. Transitions in a DSA are labeled with words. From a state, a DSA triggers an outgoing transition on seeing a word ending with the transition's label. 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, compared to DFAs. In this work, we focus on questions around finding a minimal DSA for a regular language. In this context, the number of states is not a faithful measure of the size of a DSA, since the transition-labels contain strings of arbitrary length. Hence, we consider total-size (number of states + number of edges + total length of transition-labels) as the size measure of DSAs.   We start by formally defining the model and providing a DSA-to-DFA conversion that allows to compare the expressiveness and succinctness of DSA with related automata models. Our main technical contribution is a method to derive DSAs from a given DFA: a DFA-to-DSA conversion. We make a surprising observation that the smallest DSA derived from the canonical DFA of a regular language L need not be a minimal DSA for L. This observation leads to a fundamental bottleneck in deriving a minimal DSA for a regular language. In fact, we prove that given a DFA and a number k, the problem of deciding if there exists an equivalent DSA of total-size atmost k is NP-complete.<\/jats:p>","DOI":"10.46298\/lmcs-22(2:16)2026","type":"journal-article","created":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T08:40:08Z","timestamp":1778143208000},"source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Suffix-reading Automata"],"prefix":"10.46298","volume":"Volume 22, Issue 2","author":[{"given":"R","family":"Keerthan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B","family":"Srivathsan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R","family":"Venkatesh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagar","family":"Verma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2026,5,7]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/2505.09353v5","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/2505.09353v5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T08:40:08Z","timestamp":1778143208000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/15712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-22(2:16)2026","relation":{"has-preprint":[{"id-type":"arxiv","id":"2505.09353v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2505.09353v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2505.09353","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2505.09353","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,7]]},"article-number":"15712"}}