← Back to all news
arXiv Machine Learning

Learning Canonical Register Automata over Ordered Data Domains

The paper presents a polynomial‑time active learning procedure for deterministic register automata (DRAs) over ordered data domains, covering both dense domains like the rationals and non‑dense domains such as the integers. It unifies the learning framework for these domains using membership, equivalence, and memorability queries, and shows that minimization of DRAs over the integer domain is decidable. Additionally, the authors provide improved complexity bounds for several decision problems related to DRAs over ordered domains.

Related stories

arXiv Machine Learning
Sep 24

SMT-Based Active Learning of Weighted Automata

The paper introduces an SMT-based active learning algorithm for nondeterministic weighted finite automata (WFAs), offering a practical alternative to traditional Hankel/L*-style methods. The algorithm is parametric over a chosen semiring and, upon termination, guarantees the production of minimal WFAs. Experiments demonstrate that it learns numerous minimal WFAs over both finite and infinite semirings, outperforming a naive baseline and competing with state‑of‑the‑art algorithms while yielding smaller automata and requiring less teacher interaction.

By Tiago Ferreira, Kevin Batz, Alexandra Silva
benchmarks
More like this →
arXiv Machine Learning
Sep 24

On the Sample Complexity of Active Learning with Membership Queries

The paper investigates how the ability to synthesize arbitrary queries (membership queries) changes the sample complexity of active learning compared to the traditional pool-based setting. It shows that some hypothesis classes that only achieve polynomial error decay with pool-based queries become exponentially learnable when synthesis is allowed, revealing a significant gap in learning difficulty. The authors propose sufficient conditions, provide examples, and suggest a conjectural framework to identify classes that benefit from synthesized queries.

By Ganghua Wang, Shaddin Dughmi
More like this →
arXiv Machine Learning
Jun 25

Space-Efficient Language Generation in the Limit

arXiv:2606. 25777v1 Announce Type: cross Abstract: We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency.

By Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson
safety
More like this →
arXiv AI
Jun 30

Machine-learnable Sets

arXiv:2606. 28947v1 Announce Type: cross Abstract: In this study we present a formal definition of large discrete sets having, informally, three properties: their elements are easily recognized, easily generated, and the latter tasks are easily learned from examples.

By Veit Elser, Manish Krishan Lal
More like this →
arXiv Machine Learning
Jul 15

Language Identification with Succinct Machine-Independent Traces

arXiv:2607. 12443v1 Announce Type: cross Abstract: Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of the model that might overcome the negative results for its original formulation.

By Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
llms
More like this →
arXiv Machine Learning
Aug 19

Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function

The paper establishes tight pseudo-dimension bounds for data-driven multiple hyper‑parameter tuning with structured loss functions. By refining upper bounds through real algebraic geometry and analyzing invariant connected sign cells, the authors avoid over‑counting and achieve sharper sample complexities. A multi‑regime lower‑bound framework demonstrates that these upper bounds are tight, and the approach is extended to general bi‑level validation‑loss tuning and broader semi‑algebraic applications.

By Anh Tuan Nguyen, Viet Anh Nguyen
More like this →