2026-08-16T15:33:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25116 2026-02-09T08:06:23Z ddc:004 open_access

Scalable Learning of One-Counter Automata via State-Merging Algorithms Guha, Shibashis Majumdar, Anirban Mathew, Prince Sreejith, A.V. active learning passive learning one-counter automata RPNI We propose One-counter Positive Negative Inference (OPNI), a passive learning algorithm for deterministic real-time one-counter automata (DROCA). Inspired by the RPNI algorithm for regular languages, OPNI constructs a DROCA consistent with any given valid sample set. We further present a semi-algorithm for active learning of DROCA using OPNI, and provide an implementation of the approach. Our experimental results demonstrate that this approach scales more effectively than existing state-of-the-art algorithms. We also evaluate the performance of the proposed approach for learning visibly one-counter automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shibashis Guha and Anirban Majumdar and Prince Mathew and A.V. Sreejith 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.35 urn:nbn:de:0030-drops-251168 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.35 eng https://creativecommons.org/licenses/by/4.0/legalcode