Efficient Decomposition Identification of Deterministic Finite Automata from Examples

• URL: http://arxiv.org/abs/2509.24347v2
• Date: Sun, 12 Oct 2025 05:16:57 GMT
• Title: Efficient Decomposition Identification of Deterministic Finite Automata from Examples
• Authors: Junjie Meng, Jie An, Yong Li, Andrea Turrini, Fanjiang Xu, Naijun Zhan, Miaomiao Zhang,
• Abstract summary: We study DFA decomposition identification problems (DFA-DIPs)<n>DFA-DIP approaches depend on SAT encodings derived from Augmented Prefix Tree Acceptors (APTAs)<n>One of our key innovations replaces APTA with 3-valued DFA derived directly from labeled examples.
• Score: 12.847589897236373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The identification of deterministic finite automata (DFAs) from labeled examples is a cornerstone of automata learning, yet traditional methods focus on learning monolithic DFAs, which often yield a large DFA lacking simplicity and interoperability. Recent work addresses these limitations by exploring DFA decomposition identification problems (DFA-DIPs), which model system behavior as intersections of multiple DFAs, offering modularity for complex tasks. However, existing DFA-DIP approaches depend on SAT encodings derived from Augmented Prefix Tree Acceptors (APTAs), incurring scalability limitations due to their inherent redundancy. In this work, we advance DFA-DIP research through studying two variants: the traditional Pareto-optimal DIP and the novel states-optimal DIP, which prioritizes a minimal number of states. We propose a novel framework that bridges DFA decomposition with recent advancements in automata representation. One of our key innovations replaces APTA with 3-valued DFA (3DFA) derived directly from labeled examples. This compact representation eliminates redundancies of APTA, thus drastically reducing variables in the improved SAT encoding. Experimental results demonstrate that our 3DFA-based approach achieves significant efficiency gains for the Pareto-optimal DIP while enabling a scalable solution for the states-optimal DIP.

Related papers

• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• GDEPO: Group Dual-dynamic and Equal-right-advantage Policy Optimization with Enhanced Training Data Utilization for Sample-Constrained Reinforcement Learning [14.111530312590531]
  Automated Theorem Proving (ATP) represents a fundamental challenge in Artificial Intelligence (AI)<n>We propose Group Dual-dynamic and Equal-right-advantage Policy Optimization (GDEPO)<n>GDEPO incorporates three core mechanisms: 1) dynamic additional sampling, which resamples invalid batches until a valid proof is discovered; 2) equal-right advantage, decoupling the sign of the advantage function from its magnitude (modulated by auxiliary rewards) to ensure stable and correct policy updates; and 3) dynamic additional iterations, applying extra gradient steps to initially failed but eventually successful samples to accelerate learning on challenging cases.
  arXiv  Detail & Related papers  (2026-01-11T07:34:41Z)
• AFABench: A Generic Framework for Benchmarking Active Feature Acquisition [6.922744987645169]
  We introduce AFABench, the first benchmark framework for Active Feature Acquisition.<n>We implement and evaluate representative algorithms from all major categories, including static, greedy, and reinforcement learning-based approaches.<n>Our results highlight key trade-offs between different AFA strategies and provide actionable insights for future research.
  arXiv  Detail & Related papers  (2025-08-20T14:29:16Z)
• Light-IF: Endowing LLMs with Generalizable Reasoning via Preview and Self-Checking for Complex Instruction Following [10.119219532863767]
  lazy reasoning during the thinking stage is the primary factor contributing to poor instruction adherence.<n>We propose a comprehensive framework designed to enable rigorous reasoning processes involving preview and self-checking.<n>Our Light-IF-32B model surpasses both larger open-source models such as DeepSeek-R1 and closed-source models like Doubao-1.6.
  arXiv  Detail & Related papers  (2025-08-05T07:42:00Z)
• TRIDENT: Temporally Restricted Inference via DFA-Enhanced Neural Traversal [11.042648980854485]
  TRIDENT is an inference-time algorithm that guarantees compliance with temporal constraints without requiring retraining.<n>We show that TRIDENT achieves perfect constraint satisfaction, while comparison with the state of the art shows improved efficiency and high standard quality metrics.
  arXiv  Detail & Related papers  (2025-06-11T13:14:01Z)
• Joint Transmit and Pinching Beamforming for Pinching Antenna Systems (PASS): Optimization-Based or Learning-Based? [89.05848771674773]
  A novel antenna system ()-enabled downlink multi-user multiple-input single-output (MISO) framework is proposed.<n>It consists of multiple waveguides, which equip numerous low-cost antennas, named (PAs)<n>The positions of PAs can be reconfigured to both spanning large-scale path and space.
  arXiv  Detail & Related papers  (2025-02-12T18:54:10Z)
• PIPA: Preference Alignment as Prior-Informed Statistical Estimation [57.24096291517857]
  We introduce Pior-Informed Preference Alignment (PIPA), a unified, RL-free probabilistic framework.<n> PIPA accommodates both paired and unpaired data, as well as answer and step-level annotations.<n>By integrating different types of prior information, we developed two variations of PIPA: PIPA-M and PIPA-N.
  arXiv  Detail & Related papers  (2025-02-09T04:31:30Z)
• Understanding the Logic of Direct Preference Alignment through Logic [54.272600416107146]
  We propose a novel formalism for characterizing preference losses for single model and reference model based approaches.<n>We show how this formal view of preference learning sheds new light on both the size and structure of the DPA loss landscape.
  arXiv  Detail & Related papers  (2024-12-23T16:23:13Z)
• Enhancing Test Time Adaptation with Few-shot Guidance [62.49199492255226]
  Deep neural networks often encounter significant performance drops while facing with domain shifts between training (source) and test (target) data.<n>Test Time Adaptation (TTA) methods have been proposed to adapt pre-trained source model to handle out-of-distribution streaming target data.<n>We develop Few-Shot Test Time Adaptation (FS-TTA), a novel and practical setting that utilizes a few-shot support set on top of TTA.
  arXiv  Detail & Related papers  (2024-09-02T15:50:48Z)
• DFAMiner: Mining minimal separating DFAs from labelled samples [8.196522686887713]
  DFAMiner is a passive learning tool for learning minimal separating deterministic finite automata (DFA) from a set of labelled samples. We first propose a simple and linear-time algorithm that incrementally constructs a three-valued DFA from a set of labelled samples. We then apply our tool to mining a minimal separating DFA for the labelled samples by minimising the constructed automata via a reduction to solving SAT problems.
  arXiv  Detail & Related papers  (2024-05-29T08:31:34Z)
• Regularizing Variational Autoencoder with Diversity and Uncertainty Awareness [61.827054365139645]
  Variational Autoencoder (VAE) approximates the posterior of latent variables based on amortized variational inference. We propose an alternative model, DU-VAE, for learning a more Diverse and less Uncertain latent space.
  arXiv  Detail & Related papers  (2021-10-24T07:58:13Z)

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.