First-Order Automata

Luca Geatti, Alessandro Gianola, Nicola GiganteAAAI 2025 · DOI

Abstract

This paper introduces First-Order Automata (FOA), a novel symbolic automaton model designed to capture the full expressivity of First-Order Linear Temporal Logic (FOLTL) on finite words. By bridging the gap between logic and automata for infinite-state systems, the authors provide a framework for verifying complex specifications, proving closure properties, and offering a simplified proof for the decidability of the "monodic" fragment of FOLTL. This work establishes a formal machine model for infinite-state settings where traditional propositional models fall short.

Introduction

Linear Temporal Logic (LTL) has long served as the industry standard for specifying the behavior of reactive systems. However, LTL is fundamentally propositional, making it difficult to describe systems with infinite state spaces, such as databases or programs with unbounded data types. While First-Order LTL (FOLTL) addresses this by incorporating variables, quantifiers, and relations, it is notoriously difficult to manipulate; its satisfiability is highly undecidable.

Historically, propositional LTL has benefited from a robust connection to finite-state automata (such as Büchi automata), which facilitates model checking and reactive synthesis. FOLTL has lacked a corresponding "machine" model until now. This paper introduces First-Order Automata (FOA) to fill this theoretical gap, providing a symbolic approach to represent infinite state spaces finitarily.

The First-Order Automata Model

Instead of a traditional graph with explicit states and transitions, an FOA uses first-order formulas to represent its components. This symbolic representation allows the automaton to handle infinite state spaces while maintaining a finite description of its behavior. An FOA is defined by:

  • State Signature ($\Gamma$): A set of symbols defining the structure of a "state."
  • Initial Condition ($\phi_0$): A formula describing valid starting states.
  • Transition Relation ($\phi_T$): A formula relating the current state, the current input letter, and the next state.
  • Acceptance Condition ($\phi_F$): A formula describing valid final states.

Technical Innovations

To translate FOLTL into the FOA framework, the authors introduce several key technical mechanisms:

  1. Stepped Normal Form (SNF): A recursive transformation that separates what a formula asserts about the current state from what it asserts about future or past states.
  2. Surrogates: Special predicates that act as placeholders for temporal subformulas within the transition relation. These allow the automaton to "track" the truth of complex temporal properties over time without explicit state enumeration.
  3. Determinism via Elementary Equivalence: In first-order logic, multiple non-isomorphic models can exist for the same formula. Consequently, the authors define determinism not as having a unique next state, but as having next states that are elementarily equivalent—meaning they are indistinguishable by first-order logic.

Key Insights and Properties

Closure and Robustness

The authors prove that "First-Order Regular Languages" are closed under union, intersection, concatenation, and Kleene star. This mirrors the robustness of standard regular languages and suggests that FOAs are a natural extension of finite automata to the first-order setting.

The Determinism of the Past

A significant insight of the research is that if FOLTL is restricted to past operators (e.g., "has happened"), the resulting FOA is naturally deterministic. This property is particularly valuable for runtime monitoring, where a system must make definitive decisions based on historical data.

Simplifying Monodic FOLTL

Monodic FOLTL is a known decidable fragment where temporal operators apply only to formulas with at most one free variable. The authors demonstrate that monodic FOAs can be reduced to finite-control automata. This provides a significantly simpler proof of decidability for this fragment compared to classic proofs involving complex monadic second-order logic.

Results and Evaluation

As a theoretical contribution, the paper's evaluation is based on mathematical proofs and algorithmic complexity results:

  • Expressive Equivalence: The paper proves that for every FOLTL sentence, there exists an equivalent FOA (Theorem 6).
  • Semi-decidability: The authors provide an algorithm based on Bounded Model Checking that can semi-decide the non-emptiness problem (identifying if any word is accepted by the automaton).
  • Decidability of Finite-Control FOA: If the state signature is restricted to simple propositions without relations or constants, the emptiness problem becomes fully decidable (Theorem 9).
  • Complementability: Deterministic FOAs are shown to be easily complementable, a necessary feature for many verification and synthesis algorithms.

Conclusion and Future Work

While the general emptiness problem for FOA remains undecidable—reflecting the inherent complexity of FOLTL—the introduction of FOAs provides a structured way to reason about infinite-state systems.

Future research directions include:

  • Determinization: Investigating whether non-deterministic FOAs can be converted to deterministic ones, which remains an open question.
  • Infinite Words: Extending the theory from finite words to infinite ($\omega$) words to support First-Order Büchi or Streett automata for systems that run indefinitely.
  • Practical Implementation: Integrating FOA into existing temporal reasoning tools like BLACK or the MoXI intermediate language to evaluate performance on real-world verification tasks.

Summary updated

BibTeX
@inproceedings{geatti2025first,
  author = {Luca Geatti and Alessandro Gianola and Nicola Gigante},
  title = {{First-Order Automata}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33638},
}
Figure