一句话：提出黑盒主动学习算法 OL*，在多项式时间内学习确定性单计数器自动机，并可用于近似最小化。
本文研究确定性单计数器自动机（DOCA）的主动学习问题。已有算法即使针对 DROCA、VOCA 等子类，最坏情况下也需相对于目标 DOCA 规模指数时间，且依赖灰盒的计数器值查询。作者提出黑盒算法 OL*，仅使用成员查询和最小等价查询，即可学习识别目标语言的 DOCA，其运行时间相对于最小 DOCA 规模为多项式。虽然 VOCA 最小化已知 NP 难，OL* 仍可用于 DOCA 的近似最小化，输出规模至多为最小 DOCA 规模的多项式。该结果首次实现 DOCA 的多项式时间黑盒学习，并避免额外查询类型。
We give an active learning algorithm for deterministic one-counter automata (DOCA) where the learner can ask the teacher membership and minimal equivalence queries. The algorithm called OL∗learns a DOCA in time polynomial in the size of the smallest DOCA, recognising the target language.All existing algorithms for learning DOCA, even for the subclasses of deterministic real-time one-counter automata (DROCA) and visibly one-counter automata (VOCA), in the worst case, run in exponential time with respect to the size of the DOCA under learning. Furthermore, previous learning algorithms are "grey-box" algorithms relying on an additional query type - counter value query - where the teacher returns the counter value reached on reading a given word. In contrast, our algorithm is a "black-box" algorithm.It is known that the minimisation of VOCA is NP-hard. However, OL∗can be used for approximate minimisation of DOCA. In this case, the output size is at most polynomial in the size of a minimal DOCA.
DOI 原文 ·
@inproceedings{paperbot8664,
title = {Learning Deterministic One-Counter Automata in Polynomial Time},
author = {Prince Mathew and Vincent Penelle and A. V. Sreejith},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00040}
}