{"ID":2874002,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.05762","arxiv_id":"2509.05762","title":"Scalable Learning of One-Counter Automata via State-Merging Algorithms","abstract":"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 method for combining OPNI with active learning of DROCA, 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.","short_abstract":"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 method for combining OPNI with...","url_abs":"https://arxiv.org/abs/2509.05762","url_pdf":"https://arxiv.org/pdf/2509.05762v1","authors":"[\"Shibashis Guha\",\"Anirban Majumdar\",\"Prince Mathew\",\"A. V. Sreejith\"]","published":"2025-09-06T16:28:13Z","proceeding":"cs.FL","tasks":"[\"cs.FL\",\"cs.DS\",\"cs.LO\"]","methods":"[]","has_code":false}