Active Learning of Symbolic Automata Over Rational Numbers

• URL: http://arxiv.org/abs/2511.12315v1
• Date: Sat, 15 Nov 2025 18:04:36 GMT
• Title: Active Learning of Symbolic Automata Over Rational Numbers
• Authors: Sebastian Hagedorn, Martín Muñoz, Cristian Riveros, Rodrigo Toro Icarte,
• Abstract summary: Angluin's $L*$ algorithm learns finite-state automata (DFAs) in time when provided with a minimally adequate teacher.<n>We extend $L*$ to learn symbolic automata whose transitions use predicates over rational numbers, i.e., over infinite and dense alphabets.<n>Our proposed algorithm is optimal in the sense that it asks a number of queries to the teacher that is at most linear with respect to the number of transitions, and to the representation size of the predicates.
• Score: 4.921484415160938
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the $L^*$ algorithm, introduced by Angluin. The $L^*$ algorithm learns deterministic finite-state automata (DFAs) in polynomial time when provided with a minimally adequate teacher. Unfortunately, the $L^*$ algorithm can only learn DFAs over finite alphabets, which limits its applicability. In this paper, we extend $L^*$ to learn symbolic automata whose transitions use predicates over rational numbers, i.e., over infinite and dense alphabets. Our result makes the $L^*$ algorithm applicable to new settings like (real) RGX, and time series. Furthermore, our proposed algorithm is optimal in the sense that it asks a number of queries to the teacher that is at most linear with respect to the number of transitions, and to the representation size of the predicates.

Related papers

• RaaS: Reasoning-Aware Attention Sparsity for Efficient LLM Reasoning [14.409253716114213]
  Large Language Models (LLMs) have demonstrated strong capabilities across various domains.<n>These algorithms struggle with the "impossible trinity" of accuracy, time, and memory.<n>We propose a new algorithm RaaS that identifies milestone tokens and retains their KV vectors until they are no longer needed.
  arXiv  Detail & Related papers  (2025-02-16T14:28:52Z)
• Learning to Play Against Unknown Opponents [9.346742321348366]
  We show how to efficiently construct an optimal learning algorithm when the learning agent is not constrained to no-regret.<n>All these results make use of recently developed machinery that converts the analysis of learning algorithms to the class of corresponding geometric objects known as menus.
  arXiv  Detail & Related papers  (2024-12-24T09:05:06Z)
• Active Learning of Mealy Machines with Timers [3.087487671441056]
  We present the first algorithm for query learning Mealy machines with timers in a black-box context.<n>Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a timed setting.
  arXiv  Detail & Related papers  (2024-03-04T13:20:52Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning [9.594432031144716]
  Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning. We propose a novel framework for solving NP-hard qualitative reasoning problems. We obtain a major improvement of $O*((fraccnlogn)n)$ for Allen's interval algebra.
  arXiv  Detail & Related papers  (2023-05-25T11:45:12Z)
• Automatically Bounding the Taylor Remainder Series: Tighter Bounds and New Applications [10.824474741383723]
  We present a new algorithm for automatically bounding the Taylor remainder series. Our algorithm can make efficient use of machine learning hardware, and we provide an open source implementation in JAX. In a companion paper we use our new machinery to create the first universal majorization-minimization optimization algorithms.
  arXiv  Detail & Related papers  (2022-12-22T00:43:06Z)
• Algorithms for Weighted Pushdown Automata [96.29471304123844]
  Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks.<n>We develop novel algorithms that operate directly on WPDAs.
  arXiv  Detail & Related papers  (2022-10-13T10:21:31Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We design novel cutting-plane algorithms with low "regret" -- the total distance between the true point $w*$ and the hyperplanes the separation oracle returns.
  arXiv  Detail & Related papers  (2021-06-09T05:39:05Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.