Inference of Deterministic Finite Automata via Q-Learning

• URL: http://arxiv.org/abs/2510.17386v1
• Date: Mon, 20 Oct 2025 10:23:36 GMT
• Title: Inference of Deterministic Finite Automata via Q-Learning
• Authors: Elaheh Hosseinkhani, Martin Leucker,
• Abstract summary: This paper investigates the use of Q-learning, a well-known reinforcement learning algorithm, for the passive inference of deterministic finite automata.<n>It builds on the core insight that the learned Q-function, which maps state-action pairs to rewards, can be reinterpreted as the transition function of a DFA over a finite domain.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Traditional approaches to inference of deterministic finite-state automata (DFA) stem from symbolic AI, including both active learning methods (e.g., Angluin's L* algorithm and its variants) and passive techniques (e.g., Biermann and Feldman's method, RPNI). Meanwhile, sub-symbolic AI, particularly machine learning, offers alternative paradigms for learning from data, such as supervised, unsupervised, and reinforcement learning (RL). This paper investigates the use of Q-learning, a well-known reinforcement learning algorithm, for the passive inference of deterministic finite automata. It builds on the core insight that the learned Q-function, which maps state-action pairs to rewards, can be reinterpreted as the transition function of a DFA over a finite domain. This provides a novel bridge between sub-symbolic learning and symbolic representations. The paper demonstrates how Q-learning can be adapted for automaton inference and provides an evaluation on several examples.

Related papers

• LatentQA: Teaching LLMs to Decode Activations Into Natural Language [72.87064562349742]
  We introduce LatentQA, the task of answering open-ended questions about model activations in natural language.<n>We propose Latent Interpretation Tuning (LIT), which finetunes a decoder LLM on a dataset of activations and associated question-answer pairs.<n>Our decoder also specifies a differentiable loss that we use to control models, such as debiasing models on stereotyped sentences and controlling the sentiment of generations.
  arXiv  Detail & Related papers  (2024-12-11T18:59:33Z)
• Learning Quantitative Automata Modulo Theories [17.33092604696224]
  We present QUINTIC, an active learning algorithm, wherein the learner infers a valid automaton through deductive reasoning. Our evaluations utilize theory of rationals in order to learn summation, discounted summation, product, and classification quantitative automata.
  arXiv  Detail & Related papers  (2024-11-15T21:51:14Z)
• AI-Aided Kalman Filters [65.35350122917914]
  The Kalman filter (KF) and its variants are among the most celebrated algorithms in signal processing.<n>Recent developments illustrate the possibility of fusing deep neural networks (DNNs) with classic Kalman-type filtering.<n>This article provides a tutorial-style overview of design approaches for incorporating AI in aiding KF-type algorithms.
  arXiv  Detail & Related papers  (2024-10-16T06:47:53Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• Learning Task Automata for Reinforcement Learning using Hidden Markov Models [37.69303106863453]
  This paper proposes a novel pipeline for learning non-Markovian task specifications as succinct finite-state task automata' We learn a product MDP, a model composed of the specification's automaton and the environment's MDP, by treating the product MDP as a partially observable MDP and using the well-known Baum-Welch algorithm for learning hidden Markov models. Our learnt task automaton enables the decomposition of a task into its constituent sub-tasks, which improves the rate at which an RL agent can later synthesise an optimal policy.
  arXiv  Detail & Related papers  (2022-08-25T02:58:23Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Deep Algorithmic Question Answering: Towards a Compositionally Hybrid AI for Algorithmic Reasoning [0.0]
  We argue that the challenge of algorithmic reasoning in question answering can be effectively tackled with a "systems" approach to AI. We propose an approach to algorithm reasoning for QA, Deep Algorithmic Question Answering.
  arXiv  Detail & Related papers  (2021-09-16T14:28:18Z)
• Symbolic AI for XAI: Evaluating LFIT Inductive Programming for Fair and Explainable Automatic Recruitment [11.460075612587591]
  We propose an ILP technique that can learn a propositional logic theory equivalent to a given black-box system. We show the expressiveness of LFIT for this specific problem and propose a scheme that can be applicable to other domains.
  arXiv  Detail & Related papers  (2020-12-01T09:36:59Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  We present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding.
  arXiv  Detail & Related papers  (2020-09-08T16:42:55Z)
• Explainable AI for Classification using Probabilistic Logic Inference [9.656846523452502]
  We present an explainable classification method. Our method works by first constructing a symbolic Knowledge Base from the training data, and then performing probabilistic inferences on such Knowledge Base with linear programming. It identifies decisive features that are responsible for a classification as explanations and produces results similar to the ones found by SHAP, a state of the artley Value based method.
  arXiv  Detail & Related papers  (2020-05-05T11:39:23Z)
• Learning What Makes a Difference from Counterfactual Examples and Gradient Supervision [57.14468881854616]
  We propose an auxiliary training objective that improves the generalization capabilities of neural networks. We use pairs of minimally-different examples with different labels, a.k.a counterfactual or contrasting examples, which provide a signal indicative of the underlying causal structure of the task. Models trained with this technique demonstrate improved performance on out-of-distribution test sets.
  arXiv  Detail & Related papers  (2020-04-20T02:47:49Z)

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.