Research map / Learning theory and algorithms / Combinatorial and search optimization
First-Order Automata
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines first-order automata, a symbolic automaton model over first-order words that captures FOLTL on finite words, studies its closure and decidability properties, and gives a direct proof of monodic FOLTL decidability.
Problem
FOLTL is highly expressive but undecidable in general, and there is no automaton model capturing it that would support verification, synthesis, and monitoring of infinite-state systems.
Approach
Introduces first-order automata whose states are first-order structures described symbolically by first-order sentences (initial condition, transition relation, acceptance condition), encodes any FOLTL sentence into such an automaton, shows pure-past formulas yield deterministic complete automata, and reduces monodic FOLTL decidability to finite-control automata.
Key results
- Shows first-order regular languages are closed under union, intersection, concatenation and Kleene star, and pure-past FOLTL yields deterministic complete automata (Theorem 7).
- Encodes any FOLTL sentence over any theory into a first-order automaton with language equality (Theorem 6).
- Proves monadic first-order automata are equivalent to finite-control ones (Theorem 10), giving a self-contained proof of monodic FOLTL decidability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use pure-past FOLTL sentences (no future operators) to build the first-order automaton (Encoding 2) | first-order automata from FOLTL · theoretical construction | determinism and completeness of the resulting automaton | Helped |
| Restrict state signature to monadic predicates (monodic FOLTL) and eliminate equality, then convert to finite-control automaton | monadic first-order automata · theoretical construction | decidability of emptiness | Helped |
| Restrict state signature to propositions only (finite-control automata) | first-order automata emptiness · theoretical construction | decidability of emptiness | Helped |
Surprising findings
- Determinization of first-order automata remains open, so complementation is not known to be closed.
- Emptiness is highly undecidable in general, since it subsumes FOLTL satisfiability.
Limitations
- Complementation and determinization are open questions.
- Non-emptiness is only semi-decidable under sufficient conditions.
- Only finite words are treated; infinite-word extension is left to future work.
Experimental setup
Baselines: symbolic finite automata alternating symbolic automata
Builds on: FOLTL LTLf symbolic finite automata Bounded Model Checking Gabbay et al. 2003 monodic decidability
Closest papers by meaning
- On the Expressiveness of State Space Models via Temporal Logics (ICLR 2026 · similarity 0.87)
- Characterizing the Expressivity of Fixed-Precision Transformer Language Models (NeurIPS 2025 · similarity 0.85)
- Foundations of Reactive Synthesis for Declarative Process Specifications (AAAI 2024 · similarity 0.84)
- On Action Theories with Iterable First-Order Progression (AAAI 2025 · similarity 0.84)
- Adaptive Reactive Synthesis for LTL and LTLf Modulo Theories (AAAI 2024 · similarity 0.83)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.