Finite-State Machine

Also known as FSM

Follow this topic Ask about this topic

Latest papers

18 papers5 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Oct 10, 2026

StateSkill-Agent: An Effective and Efficient Embodied Agent via State-conditioned Skill

In this work, we aim to develop an embodied MLLM agent that understands and solves embodied tasks by learning, abstracting, and reusing transferrable and generalizable behavioral patterns. To this end, we propose StateSkill, a new skill representation for embodied agents, which introduces the concept of "finite-state machines" into skill modeling for effective and efficient skill construction and learning. The core idea of StateSkill is to model embodied interaction experiences as a finite-state machine, where a skill is organized around a set of task-progress states, state transitions, and state-conditioned guidance, enabling embodied agents to dynamically adjust their skills as the task progresses while keeping skill contexts compact and stage-relevant. We further develop StateSkill-Evolve, an experience-driven evolution mechanism that iteratively refines StateSkill through retrospective analysis of new successful and failed state-guided trajectories. Upon this, we introduce StateGRPO, which integrates StateSkill evolution and model optimization via state-conditioned GRPO into a unified iterative learning loop, enabling state-conditioned skills and model capabilities to co-evolve and reinforce each other. Extensive experiments demonstrate the effectiveness of our proposed methods and trained model (i.e., StateSkill-Agent) across various embodied tasks.

Changxu Wei, Jingyi Zhang, Zhiyu Zheng +6

The Hong Kong Polytechnic University · ACE Robotics · Nanyang Technological University +3

Finite-State Machine LLM Agent Skill Learning Agent Skill Learning Embodied AI RL for LLM Agents

Sep 28, 2026

Grab a Coffee: Future-Aware Guidance for Discrete Diffusion with Compiled Objectives

Discrete diffusion models generate sequences by iteratively resolving multiple tokens in parallel, offering a flexible alternative to left-to-right generation. However, guiding this process with a sequence-level objective is difficult because the value of one unresolved token depends on the other tokens with which it can form a high-reward sequence. Enumerating all such completions makes the whole guidance computation grow exponentially with the number of unresolved positions. We introduce COFFEE, a plug-and-play framework that avoids this enumeration by separating sequence dependence from the objective. At each diffusion step, a target-free carrier absorbs the marginal token distributions predicted by the denoiser to construct a joint model over the unresolved tokens, while a compiled finite-state model records how their combinations affect the sequence-level preference. Pairing their states allows COFFEE to transfer global preferences to unresolved positions and sample a clean reconstruction without retraining the diffusion model. The same framework supports explicit hard constraints and learned soft objectives. We evaluate COFFEE across multiple symbolic, language, and biological benchmarks, where it achieves strong control results with task-dependent quality and diversity trade-offs. By making objectives available to inference rather than only evaluation, COFFEE brings joint conditioning, completion-weighted guidance, and optimization-based constraints into pretrained neural generation, showing the potential of neural-symbolic methods in diffusion guidance.

Hua, Xu, Dongxin Li +4

Edward · Data Science and Analytics Thrust, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China · Department of Computer Science, University of California, Los Angeles, USA +1

Constrained Generative Modeling Diffusion Model Guidance Finite-State Machine Diffusion Models

Sep 26, 2026

Length-Independent State Tracking Under a Parallel Scan

Learning robust and scalable finite-state tracking is fundamental to sequence processing. While linear recurrent neural networks (RNNs), linear attention, and state space models enable scalable parallel training through affine recurrences, their theoretical expressivity guarantees assume idealized arithmetic and do not extend to finite precision, where the parallel scan that makes them fast is itself a source of perturbation. We formalize finite-state tracking at finite precision and characterize length independence: tracking that stays correct at every sequence length, at a precision cost that does not grow with the length. We show that length-independent state tracking requires two competing dynamics within a single map: contraction to suppress numerical perturbations and separation to keep distinct states apart. We prove that affine recurrences, which offer a single rate at each step to serve both roles, realize at most definite automata at finite precision. Instead of treating scan compatibility as a restriction on the update map, we reinterpret it as a computational budget and introduce the Neural Finite-State Machine (NFSM): a nonaffine, scan-compatible RNN built for length-independent finite-state tracking. On synthetic benchmarks spanning abelian and nonabelian groups, noninvertible monoids, and textual state-tracking tasks, affine baselines fail on every nondefinite task, most of them within a few hundred steps. A single NFSM layer instead learns the exact transition tables of every algebraic task, which certifies correctness beyond the tested lengths, and a stack of NFSMs keeps perfect accuracy on the textual tasks at every tested length.

Julien Brandoit, Arthur Fyon, Thomas Braipson +5

Montefiore Institute, University of Liège Liège, Belgium

Finite-State Machine Recurrent Neural Networks Sequence Modeling Linear RNNs

Sep 24, 2026

HEXIS: Compiling Agent Skills into Extended Finite State Machines

Agent skills provide instructions and reusable knowledge, yet agents have to frequently infer which action to take next. This skill's execution paradigm combines task reasoning with control decisions, which could cause the agent to act improperly or omit necessary steps. To improve agent compliance for skills, we introduce HEXIS, which compiles agent skills into extended finite state machines (FSM) that separate knowledge from control flow. Skill knowledge is incorporated into local instructions that guide reasoning and generation within states. The machine records execution progress and intermediate results, while explicit transition conditions determine subsequent operations. Our incremental compiler first maps skill clauses and tool interfaces to state operations, local instructions, data bindings, and transitions. It then aligns development traces with existing states to identify missing operations and dependencies. These are incorporated by adding or reusing states and refining their connections. Updates are accepted only after static checks and replay of the current and all previously accepted traces. Across four benchmarks and four executors, HEXIS improves success over Skill + ReAct by 16.2 percentage points on average. Qwen3.8-27B reduces execution tokens by 38.4-88.9% across benchmarks.

Minghao LI

LLM Agent Skill Learning Finite-State Machine

Sep 24, 2026

Towards An LLM-Driven Unified Conversion Framework for BT and FSM in Autonomous Intelligent Systems

Finite state machine (FSM) and behavior trees (BT) are widely adopted behavioral modeling paradigms for autonomous intelligent systems. While functionally equivalent and inter-convertible in principle, existing transformation methods between FSM and BT face major challenges in preserving behavioral completeness and avoiding model complexity explosion. To overcome these issues, we propose an LLM-driven unified conversion framework that enables automatic, efficient, and semantically consistent transformation between FSM and BT. Specifically, a novel loop execution BT structure is designed for LLM to accurately capture the loop structure in FSM, thereby preserving behavioral completeness. To mitigate the state explosion problem in BT-to-FSM conversion, a depth compression strategy is introduced with LLM prompt to eliminate redundant control nodes, complemented by differentiated hierarchical conversion rules that collectively reduce the number of required sub-FSM. Simulation experiments in multiple autonomous decision-making scenarios demonstrate that the proposed framework enables an accurate and automated bidirectional conversion between FSM and BT. Furthermore, it significantly enhances the scalability and maintainability of generated models compared to traditional approaches, providing a practical solution for behavior model conversion in consumer-grade autonomous intelligent systems such as service robots, game agents, and smart home devices

Zhang Qi, Yang Shuo, Zhu Zhengqiu +2

College of Systems Engineering, National University of Defense Technology CHANGSHA, HUNAN, China

Finite-State Machine Behavior Trees

Aug 24, 2026

Automata from Agent Traces: Failure and Next-Step Prediction

LLM-based agents execute multi-step tasks, but their behavioral structure remains opaque: long unstructured traces resist the safety auditing and runtime monitoring that deployment requires. Existing approaches operate per-trace or success-only, so they miss the cross-run topology that links next-step and failure prediction. To recover that shared structure, we collapse an entire trace corpus into a single, compact finite-state machine (FSM) that serves as a structural substrate for the otherwise unpredictable behavior of LLM agents. Across twelve public datasets, the FSMs are compact (7-43 states), replay held-out data at >=0.997 fitness with near-identical topology across splits, and build in milliseconds. This substrate addresses both prediction goals. For next-step prediction, FSM-state context outperforms Agent Workflow Memory on every ground-truth-matched dataset. For failure prediction, per-state behavioral features reach held-out AUROC up to 0.94, and an online monitor ranks failing runs above passing ones from a partial trace, triggering early stopping well before completion. Behavioral topology thus appears shaped more by the deployment harness than by the LLM, providing a model-agnostic structural primitive for safety auditing and runtime monitoring.

Seonglae Cho, Franklin Cardenoso Fernandez, Umar Mohammed +4

Holistic AI · PUC-Rio · University College London

AI Agent Monitoring AI Agent Auditing LLM Agent Reliability Next-Action Prediction Finite-State Machine

Jul 7, 2026

When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?

Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with

B

bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set

M

at a cost of only

\log_2 |M| + O(1)

additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool, namely a tape supporting only local

\mathtt{read}

,

\mathtt{write}

, and

\mathtt{move}

commands, makes the system Turing complete: for every single-tape Turing machine with state set

Q

and tape alphabet

Γ

, a controller with

O(\log |Q| + \log |Γ|)

bits of internal memory simulates it, and we exhibit a concrete exponential separation:

\mathrm{EQ}_n

requires

2^n

states without tools but a single constant-size controller with the tape tool. Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states,

\{0,1\}

transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation, where

O(\log B)

recurrent bits suffice to simulate any

B

-state Turing machine, and prove a matching impossibility result.

Nikola Zubić, Qian Li, Yuyi Wang +1

Robotics and Perception Group, University of Zurich · Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data · Tengen Intelligence Institute, CRRC Zhuzhou Institute

Recurrent Neural Networks Neural Network Expressivity Finite-State Machine

Jun 29, 2026

Destination-Labeled Self-Looping Systems with Dwell: Intrinsic Characterization, Realization Cost, and Recognition

We study a finite-state symbolic controller for systems in which the admissible visible transitions are fixed in advance and each visible state carries a minimum dwell requirement. The resulting model, which we call a destination-labeled self-looping system with dwell (DLSL system), records the visible graph together with local decision maps; dwell memory appears only after phase expansion. The main structural issue is that, once dwell is imposed, the current visible state no longer determines whether a departure is allowed. This leads to the converse problem: which deterministic transducers arise as phase-expanded realizations of DLSL systems over a fixed visible graph? We show that the answer is exactly the class of fiber-linear graph-respecting transducers. Under natural reachability and realizable-departure assumptions, equivalent accessible realizations over the same visible graph are isomorphic; in particular, the visible transduction determines the dwell vector and the local decision maps. We also prove that any graph-preserving deterministic realization enforcing dwell values

(d_i)

requires exactly

\sum_i d_i

control states. Finally, we give an

O(|Q||Ω|)

recognition and reconstruction procedure, and extend the analysis to an edge-entry variant in which transitions may enter interior phases of successor fibers.

Reda Belaiche

Department of Computer Science, University Institute of Technology of Créteil-Vitry, Paris-Est Créteil University, 122 rue Paul Armangot, Vitry-sur-Seine, 94400, France

Finite-State Machine

Jun 1, 2026

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

Generations from large language models often fail to conform to desired constraints such as JSON schema. Existing locally constrained decoding (LCD) approaches enforce constraints by myopically masking out next tokens, resulting in biased sampling and degradation in performance. Recent work uses sequential Monte Carlo (SMC) methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge. In this work, we propose a generic approach to construct proposals and potentials for SMC sampling from

p_{\mathrm{lm}}( \cdot \mid \mathrm{constraint})

. First, we show that constraints specified as finite automata can be tensorized for efficient execution on GPUs, which we use to construct globally constrained decoding (GCD) proposals. In addition, leveraging the fact that tensorized finite automata share the same circuit structure as hidden Markov models, we circuit-multiply them to obtain the probabilistic GCD (P-GCD) proposals encoding both logical and probabilistic information about the target distributions. We evaluate (P-)GCD on the tasks of function calling, keyword-based generation, and SQL generation. Experiments show that under the same SMC sampling setup, compared to LCD proposals, (P-)GCD converges faster to the target distribution with significantly fewer particles.

Meihua Dang, Linxin Song, Honghua Zhang +3

Department of Computer Science, Stanford University · Department of Computer Science, University of Southern California · Department of Computer Science, University of California, Los Angeles

Constrained Generative Modeling Constrained Decoding Finite-State Machine Constrained Sampling

May 7, 2026

PrefixGuard: Online Failure Warning and Trace-Grounded Diagnosis for LLM Agents

Large language model (LLM) agents execute multi-step tasks, but terminal verdicts arrive too late for intervention. Agent traces mix messages, tool calls, and feedback, making it difficult to learn failure signals from terminal outcomes. Even if a model learns to predict failure from execution prefixes, its predictions alone cannot show which actions, feedback, or unmet conditions need inspection. Existing work studies online failure prediction and diagnosis from completed trajectories, yet few methods connect timely warning to a compact symbolic model of execution behavior. We introduce PrefixGuard, a neuro-symbolic method that uses learned events to connect online failure warning with finite-state execution diagnosis. A gated recurrent unit (GRU) predicts horizon-specific failure risk from these events. A deterministic finite automaton (DFA) organizes their histories into compact risk-labeled paths for replay and rule-monitor composition. Across all 24 benchmark--horizon settings, PrefixGuard exceeds the strongest evaluated baseline in mean test area under the precision--recall curve (AUPRC). Average gains range from 12.0 to 21.9 percentage points. At a nominal 10% FAR budget, averaged test recall spans 56.1%--93.0% across benchmarks. On one frozen

τ^2

-Bench DFA, model checking five specifications identifies violations in 21 of 265 benchmark-successful runs.

Xinmiao Huang, Jinwei Hu, Qisong He +4

University of Liverpool · Université Grenoble Alpes

Fault Detection AI Agent Monitoring Finite-State Machine Neuro-Symbolic AI LLM Agent Reliability Fault Diagnosis

Apr 29, 2026

Enforcing Benign Trajectories: A Behavioral Firewall for Structured-Workflow AI Agents

Structured-workflow agents driven by large language models execute tool calls against sensitive external environments. We propose \codename, a telemetry-driven behavioral anomaly detection firewall. Drawing on sequence-based intrusion detection, \codename\ compiles verified benign tool-call telemetry into a parameterized deterministic finite automaton (pDFA). The model defines permitted tool sequences, sequential contexts, and parameter bounds. At runtime, a lightweight gateway enforces these boundaries via an

O(1)

state-transition structural lookup, shifting computationally expensive analysis entirely offline. Evaluated on the Agent Security Bench (ASB), \codename\ achieves a 5.6% macro-averaged attack success rate (ASR) across five scenarios. Within three structured workflows, ASR drops to 2.2%, outperforming Aegis, a state-of-the-art stateless scanner, at 12.8%. \codename\ achieves 0% ASR on multi-step and context-sequential attacks in structured settings. Furthermore, against 1,000 algorithmically spliced exfiltration payloads, only 1.4% matched valid structural paths, all of which failed end-to-end string parameter guards (0 successes out of 14 surviving paths, 95% CI [0%, 23.2%]). \codename\ introduces just 2.2~ms of per-call latency (a 3.7

\times

speedup over Aegis) while maintaining a 2.0% benign task failure rate (BTFR) on benign workloads. Modeling the behavioral trajectory effectively collapses the available attack surface, but unmaintained continuous parameter bounds remain vulnerable to synonym-substitution attacks (18% evasion rate). Thus, exact-match whitelisting of sensitive parameters ultimately bears the final defensive load against execution.

Hung Dang

Van Lang University, Ho Chi Minh City, Vietnam

LLM Agent Security AI Agent Monitoring Safety Filtering Finite-State Machine Tool Access Control for LLM Agents Anomaly Detection

Apr 20, 2026

SDOF: Taming the Alignment Tax in Multi-Agent Orchestration with State-Constrained Dispatch

Multi-agent orchestration frameworks such as LangChain, LangGraph, and CrewAI route tasks through graph-based pipelines but do not enforce the stage constraints that govern real business processes. We present SDOF, a framework that treats multi-agent execution as a constrained state machine. SDOF operates through two primary defensive layers, implemented by three components: (1) an Online-RLHF Specialized Intent Router trained via Generative Reward Modeling (GRPO) and (2) a StateAwareDispatcher with GoalStage finite-automaton checks and precondition/postcondition SkillRegistry validation for auditable execution control. On a recruitment system backed by the Beisen iTalent platform (6000+ enterprises), 185 expert-curated scenarios trigger 1671 live API calls. Our GSPO-aligned 7B Intent Router achieves higher joint accuracy than zero-shot GPT-4o on this FSM-constrained adversarial routing benchmark (80.9% versus 48.9%). In end-to-end execution, SDOF reaches 86.5% task completion (95% confidence interval 80.8 to 90.7) and blocks all 22 operations in the injection, illegal HR subset. Under a broader message-level blocking audit, SDOF attains precision 100% and recall 88%, expert agreement kappa=0.94. A separate evaluation on 960 SGD-derived dialogues spanning 8 service domains surfaces 201 stage-order conflicts under our FSM mapping, 41 of which arise in the normal split. This arXiv version reports the current validated scope; extended multi-seed training comparisons and deeper workflow evaluations will be released in a subsequent update.

Zhantao Wang

Digital China

Multi-Agent Orchestration AI Agent Safety Finite-State Machine LLM Agent Routing

Apr 3, 2026

NetAgentBench: A State-Centric Benchmark for Evaluating Agentic Network Configuration

As agentic network management gains popularity, there is a critical need for evaluation frameworks that transcend static, one-shot testing. To address this, we introduce NetAgentBench, a dynamic benchmark that evaluates agent interactions through a Finite State Machine (FSM) formalization guaranteeing determinism, correctness, and bounded execution. This provides the networking landscape with a rigorous foundation to measure complex, multi-turn operational behaviors. Our empirical evaluation of four state-of-the-art LLM agents through diverse network configuration tasks reveals stark deficiencies: while agents can solve basic tasks, they suffer severe exploration meltdowns and coherence collapse during expert-level configurations. Ultimately, NetAgentBench demonstrates that systematically evaluating multi-turn behavioral stability is an indispensable step toward realizing trustworthy, fully autonomous networks.

Ahmed Twabi, Yepeng Ding, Tohru Kondo

Informatics & Data Science, Hiroshima University, Hiroshima, Japan

Finite-State Machine LLM Agent Evaluation AI Agent Benchmarks AI Agent Reliability

Apr 2, 2026

PAC learning PDFA from data streams

This is an extended version of our publication Learning state machines from data streams: A generic strategy and an improved heuristic, International Conference on Grammatical Inference (ICGI) 2023, Rabat, Morocco. It has been extended with a formal proof on PAC-bounds, and the discussion and analysis of a similar approach has been moved from the appendix and now has a full dedicated section. State machine models are models that simulate the behavior of discrete event systems, capable of representing systems such as software systems, network interactions, and control systems, and have been researched extensively. The nature of most learning algorithms however is the assumption that all data be available at the beginning of the algorithm, and little research has been done in learning state machines from streaming data. In this paper, we want to close this gap further by presenting a generic method for learning state machines from data streams, as well as a merge heuristic that uses sketches to account for incomplete prefix trees. We implement our approach in an open-source state merging library and compare it with existing methods. We show the effectiveness of our approach with respect to run-time, memory consumption, and quality of results on a well known open dataset. Additionally, we provide a formal analysis of our algorithm, showing that it is capable of learning within the PAC framework, and show a theoretical improvement to increase run-time, without sacrificing correctness of the algorithm in larger sample sizes.

Robert Baumgartner, Sicco Verwer

Department of Software Technology, Delft University of Technology, Delft, The Netherlands

Automata Learning Finite-State Machine Streaming Algorithms PAC Learning

Mar 31, 2026

Designing FSMs Specifications from Requirements with GPT 4.0

Finite state machines (FSM) are executable formal specifications of reactive systems. These machines are designed based on systems' requirements. The requirements are often recorded in textual documents written in natural languages. FSMs play a crucial role in different phases of the model-driven system engineering (MDE). For example, they serve to automate testing activities. FSM quality is critical: the lower the quality of FSM, the higher the number of faults surviving the testing phase and the higher the risk of failure of the systems in production, which could lead to catastrophic scenarios. Therefore, this paper leverages recent advances in the domain of LLM to propose an LLM-based framework for designing FSMs from requirements. The framework also suggests an expert-centric approach based on FSM mutation and test generation for repairing the FSMs produced by LLMs. This paper also provides an experimental analysis and evaluation of LLM's capacities in performing the tasks presented in the framework and FSM repair via various methods. The paper presents experimental results with simulated data. These results and methods bring a new analysis and vision of LLMs that are useful for further development of machine learning technology and its applications to MDE.

Omer Nguena Timo, Paul-Alexis Rodriguez, Florent Avellaneda

Universit´e du Qu´ebec en Outaouais, Quebec-Canada · Universit´e Paris-Saclay, Paris-France · Universit´e du Qu´ebec `a Montr´eal, Qu´ebec-Canada

Finite-State Machine Model-Based Systems Engineering Automated Program Repair

Mar 20, 2026

Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability

We present a formal and constructive framework for simulating Alternating Finite Automata (AFAs) using Logic-Gated Time-Shared Feedforward Networks (LG-TS-FFNs). Unlike prior neural automata models limited to Nondeterministic Finite Automata (NFAs) and existential reachability, our architecture integrates learnable, state-dependent biases that function as differentiable logic gates, enabling the representation of both Existential OR and Universal AND aggregation within a shared-parameter linear recurrence. We prove that this architectural modification upgrades the network's computational class to be structurally isomorphic to AFAs, thereby inheriting their exponential succinctness: the network can represent regular languages requiring

2^n

states in an NFA with only

n

neurons. We rigorously establish that the forward pass of an LG-TS-FFN exactly simulates the reachability dynamics of an AFA, including instantaneous

\varepsilon

-closures. Furthermore, we demonstrate empirical learnability: a continuous relaxation of the logic gates allows the network to simultaneously recover the automaton's topology and logical semantics from binary labels via standard gradient descent. Extensive experiments confirm that our model achieves perfect recovery of ground-truth automata, bridging the gap between statistical learning and succinct, universal logical reasoning.

Sahil Rajesh Dhayalkar

Arizona State University

Differentiable Logic Automata Learning Finite-State Machine Feedforward Neural Networks Differentiable Logic Gate Networks Neuro-Symbolic Reasoning

Mar 2, 2026

Boosting AI Reliability with an FSM-Driven Streaming Inference Pipeline: An Industrial Case

The widespread adoption of AI in industry is often hampered by its limited robustness when faced with scenarios absent from training data, leading to prediction bias and vulnerabilities. To address this, we propose a novel streaming inference pipeline that enhances data-driven models by explicitly incorporating prior knowledge. This paper presents the work on an industrial AI application that automatically counts excavator workloads from surveillance videos. Our approach integrates an object detection model with a Finite State Machine (FSM), which encodes knowledge of operational scenarios to guide and correct the AI's predictions on streaming data. In experiments on a real-world dataset of over 7,000 images from 12 site videos, encompassing more than 300 excavator workloads, our method demonstrates superior performance and greater robustness compared to the original solution based on manual heuristic rules. We will release the code at https://github.com/thulab/video-streamling-inference-pipeline.

Yutian Zhang, Zhongyi Pei, Yi Mao +3

School of Software, BNRist, Tsinghua University, China · Tianyi Technology Co., Ltd, China

Streaming Inference Finite-State Machine Distribution Shift Robustness Object Counting

Jan 18, 2026

Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

It is well known that computing a minimum deterministic finite automaton consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the case where the input sample is prefix-closed. This formulation is equivalent to computing a minimum Moore machine consistent with observations along its runs. We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings. Furthermore, we show that the problem remains NP-hard as a decision problem even when the sample set consists of the prefixes of a single binary string. Our argument also extends to the corresponding problem for Mealy machines.

Radu Cosmin Dumitru, Ryo Yoshinaka, Ayumi Shinohara

Delft University of Technology, Delft, Netherlands · Tohoku University, Sendai, Japan

Finite-State Machine