A General Automata Model for First-Order Temporal Logics (Extended Version)
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "A General Automata Model for First-Order Temporal Logics (Extended Version)".
Jane: Here's the gist of the paper. First-order automata are defined as a model capable of capturing first-order temporal logic on finite words, showing how they can capture any FOLTL formula over any signature and theory The paper introduces this new class of automata and the corresponding notion of regular first-order languages, demonstrating their closure under common language-theoretic operations It shows how these automata can encode any FOLTL sentence over any first-order theory and provides conditions for the semidecidability of their non-emptiness problem Ultimately, the formalism is shown to be useful by proving the decidability of monodic FOLTL on finite words.
Tom: Pruning redundant reasoning tokens The paper defines first-order words as sequences of T-structures where rigid symbols have constant interpretations throughout the word It then defines FOLTL formulas using a syntax involving terms, predicates, and temporal operators like X, Y, U, and S The semantics for satisfaction is detailed by defining how formulas are interpreted over non-empty first-order words based on time points in the word A FOLTL sentence is satisfiable if its T-language LT(φ) is not empty.
Jane: How the training signal is built The authors introduce a symbolic representation for infinite state spaces using first-order logic, defining a first-order automaton A = hΣ, Γ, φ0, φT, φF i The automaton induces runs (sequences of states) when reading a T-word The acceptance condition is defined as a standard reachability condition based on the final state condition φF i.
Tom: Where the gains come from The paper establishes several key results regarding the expressive power and decidability of these automata 1.
Title and authors: Tom: So we’re talking about this new model today, the "A General Automata Model for First-Order Temporal Logics (Extended Version)" paper. It sounds like they are trying to build a system that can actually handle first-order temporal logic on finite words, which is pretty ambitious.
Jane: That's right, Tom. Basically, the logic itself is flexible enough to describe complex behaviors and properties in systems with time, but capturing that with a standard automaton has been a missing piece for verification work.
Lu: The authors define this new class of automata and the regular first-order languages they create. They show how these capture any first-order temporal logic over any signature and theory, which is a big step because usually, you're stuck with simpler logics or much more complex models.
Meng: Okay, so they claim this model can encode any first-order temporal logic sentence over any specific theory, which means it should be able to represent a huge range of system behaviors. But how does that actually translate into something we can use in practice?
Tom: Well, they define these things as first-order words as sequences of T structures where rigid symbols stay the same throughout the word, and they build the automaton using a symbolic representation that exploits first-order logic to represent those infinite state spaces in a finite way.
Jane: That sounds like they are taking something that is inherently infinite, like a long sequence of events, and giving it a finite structure so we can actually compute with it. They define the semantics by looking at satisfaction over non-empty first-order words based on time points in that word.
Lu: They’re showing how FOLTL sentences are satisfiable if the T language of that sentence isn't empty, which is the standard way to think about it, but they are using this new automaton structure to make that check possible symbolically.
Meng: So, if I have a temporal requirement for a system, like "this state must eventually be reached," this paper suggests we can translate that into a first-order automaton. What's the main thing they prove about these models?
Tom: They show closure under common language-theoretic operations. This means if you can do some standard operations like union or intersection on these first-order regular languages, this new class of automata can also do those things.
Jane: That’s important because it means we don't have to invent a whole new set of tools just to combine different temporal constraints; the structure they define is robust enough for common language operations.
Lu: They also show how pure-past sentences result in deterministic first-order automata, which they say is crucial for reactive synthesis and monitoring in real systems. That’s a specific application where this construction becomes very powerful.
Meng: Reactive synthesis sounds like a big deal when you're trying to build control systems that can react correctly to things happening over time, but I worry about the size of these resulting automata. What does that imply for deployment?
Title and authors: Tom: They address the non-emptiness problem for these first-order automata by giving sufficient conditions for it to be semidecidable, and they even provide a semi-decision procedure under certain conditions on the initial and final conditions.
Jane: That’s a huge win because the general satisfiability problem for FOLTL is undecidable, but they're showing us exactly when we can actually check if a formula has any solution in this model.
Lu: They also show that monodic FOLTL on finite words is decidable, which they prove self-contained using results from monadic second order logic over (N, <). That’s a classic result being tackled directly here.
Meng: Okay, so if we only look at the simplest version of temporal logic—the monadic one—they can actually give us a definite yes or no answer on whether a requirement is possible to meet in a finite sequence of time points. That's something I could use for checking small, bounded safety properties.
Tom: And they also show how to recover decidability by restricting the state signature to finite-control or monadic automata, which gives us more concrete tools when we need practical answers.
Jane: It’s interesting how they connect this abstract logic modeling back to things like finite-control automata, which we already know how to handle in a very practical way.
Lu: They also show encodings for different things, like translating monadic automata into equivalent finite-control ones and encoding data-aware processes modulo theories, which suggests connections to other areas like data control automata.
Meng: Data-aware processes modulo theories sounds relevant for systems where the rules change based on the data flowing through them, but I need to know how much overhead this adds when you try to run it at scale.
Tom: They show that a T-run of a data control automaton is also a T-run of its encoding, which seems like a good way to maintain consistency between the abstract model and the concrete process running on hardware.
Jane: So, overall, this paper provides a solid foundation for using first-order automata as a proper tool to reason about FOLTL, especially in areas like reactive synthesis where you need that deterministic automaton structure.
Lu: They compare these first-order automata to other infinite-state models like timed automata and hybrid automata, suggesting they are still a valuable tool even when we move into those more complex settings.
Meng: If we look ahead, the authors suggest lifting these first-order automata to infinite words, but that sounds like a massive jump in complexity that would require us to completely rebuild the theory for omega-regular languages.
Tom: That’s true; moving from finite words to infinite words is where the real challenge lies for extending this formalism. They also point toward using SMT technology and property-directed reachability techniques for model checking in those more infinite settings.
Jane: It seems like the path forward involves using these deterministic constructions from pure-past FOLTL to help build reactive synthesis tools, even if we have to use more advanced verification methods later on.
Title and authors: Lu: The connection they make between the pure-past fragments and deterministic automata is a key piece for practical applications in monitoring systems, where you need to check reachability to final states efficiently.
Meng: So, for my deployment concerns, it suggests that if we can restrict our temporal requirements to those pure-past fragments, we might be able to achieve a deterministic finite automaton of singly exponential size without needing that extra determinization step. That would be a significant reduction in computational cost compared to what I was expecting.
Tom: Exactly. They show that for pure-past LTL plus past fragments, you can get that EXPTIMEcomplete complexity instead of the 2EXPTIMEcomplete complexity we might otherwise face, which is better for practical synthesis <ref:2405.20057#pg1>.
Jane: That’s a concrete gain in terms of performance for reactive systems because it simplifies the required computational steps.
Lu: And they also showed that pure-past LTL plus past fragments can be handled by a deterministic finite automaton of singly exponential size, which is a more manageable complexity class than what we thought was necessary.
Meng: So, to recap for deployment: if we use these pure-past constructions, we might get away with that singly exponential size automaton without needing the extra determinization step that seemed unavoidable before.
Tom: And they also showed how to check emptiness for monadic first-order automata by translating them into equivalent finite-control automata using a theorem, which gives us a more decidable path in those restricted cases.
Jane: It's good to see those specific decidability results because they give us concrete boundaries on what kind of temporal requirements we can actually solve with these models.
Lu: And for the monadic case, that translation shows how closely tied these structures are, which is useful when trying to verify things about simpler logic fragments.
Meng: I just want to make sure that when we build our actual systems, we're not over-complicating things by trying to use this general first-order structure for every problem if a simpler automaton will do the job.
Tom: That’s fair. The paper is showing us the power of this general model, but it also points toward these more restricted cases where we can get concrete decidability results and more manageable complexity bounds.
Jane: So, to wrap up on this paper, "A General Automata Model for First-Order Temporal Logics (Extended Version)," it gives us a solid framework connecting first-order temporal logic to a new class of automata that is useful for specifying complex systems.
Lu: The main implication is showing how these automata can capture FOLTL, and the self-contained proof of monodic FOLTL on finite words is particularly important for establishing those decidability results.
Meng: For me, the practical implication is seeing how to construct deterministic automata from pure-past formulas to make reactive synthesis more efficient in terms of complexity class.
Tom: And ultimately, it gives us a blueprint for thinking about monitoring infinite-state systems by leveraging these constructions and focusing on the specific fragments where we can get solid results.
The paper's summary: Tom: So we’re wrapping up this look at the new model today, and what we’re seeing is this paper introducing a whole new way to think about temporal logic using first-order automata. It shows how you can capture any first-order temporal logic formula over any signature and theory.
Jane: That sounds incredibly broad, Tom. So when you put that in plain English, it means this new system isn't just for simple time sequences; it can handle the complex rules of systems we see everywhere in the real world.
Tom: Exactly. They’re defining these first-order words as sequences of T structures where symbols stay constant, and then they build an automaton using first-order logic to represent those infinite state spaces in a finite way.
Jane: And what’s the big payoff here? They show that this setup can encode any complex temporal logic sentence over any given theory, which is huge because it means we can model a much wider range of behaviors than before.
Tom: Right. The main thing they prove is that this formalism allows us to check if a formula has any solutions by looking at the T language, and they give us conditions for when that checking problem becomes semidecidable.
Jane: Semidecidable is good because it means we can at least find an answer sometimes, even if it takes a long time. But the paper also hammers home that pure-past logic results in deterministic automata, which is really important for building reactive systems.
Tom: That’s the key part for me. Deterministic automata mean we don't have to deal with non-deterministic headaches when we try to build something that needs to react quickly, like monitoring a system in real time.
Jane: And they even show that if you look at just the monadic version of this logic—the simplest kind—you can translate it into a finite-control automaton, which makes proving decidability for those specific cases much cleaner.
Tom: It’s all connected to this idea of encoding. They show how to take things like symbolic finite automata and translate them into these first-order ones using just one constant and predicates that describe the rules.
Jane: So the paper is essentially giving us a toolkit where we can take a complex temporal requirement, translate it into this structured automaton, and then use those known logic rules to figure out if that requirement is possible to meet in any finite time sequence.
Tom: It’s like they’re building the engine for checking system properties by mapping the property directly onto a specific type of machine structure.
Jane: And that leads us into how we can actually use this for monitoring things running right now, especially when we look at those pure-past fragments and how they relate to finding final states. (Sound of gentle, rhythmic driving noise fades slightly)
The paper's improvements: Tom: So we’re looking at how this paper builds on its own ideas, and what they suggest we do next for these first-order automata. It seems like they aren't just stopping at defining the model; they’re actually proposing ways to use it better for practical applications.
Jane: That makes sense. So after setting up this general model, what are the actual upgrades? Are they making it faster or more accurate for real systems?
Tom: They suggest that when you deal with pure-past temporal logic, you can build a deterministic automaton from that formula without needing an extra step to make it deterministic later. That’s a direct way to make reactive synthesis more efficient.
Jane: So the naive question is, how does this translate into something we can actually deploy on hardware? And the answer seems to be that by using pure-past formulas, you can get a deterministic finite automaton of singly exponential size without that extra determinization step.
Tom: Right. That means for those specific pure-past fragments, you get a complexity class of EXPTIMEcomplete instead of what we thought was 2EXPTIMEcomplete, which is a real win for the system designers <ref:2405.20057#pg1>.
Jane: That’s concrete because it means the required computation scales better on actual hardware than if we had to go through that extra deterministic check. But what about the general case?
Tom: For pure-past fragments, they show how to leverage that deterministic automaton construction as a key piece for runtime verification by checking reachability to final states. That’s still useful even in the infinite-state setting.
Jane: It sounds like they’re using those pure-past tools as a foundation, even when dealing with more complex systems that aren't strictly pure-past.
Tom: And for the general case, they point toward using SMT technology and property-directed reachability techniques for model checking when we move into those infinite-state scenarios. That’s where the heavy lifting is needed next.
Jane: So, what does this mean for someone just listening to the show? It means that while this paper gives us a powerful way to *model* complex logic, if you want to actually verify it on a huge system, you’ll still need those advanced SMT tools.
Tom: Exactly. The paper isn't saying "this is the final answer"; it’s pointing toward the next steps for how we can use these deterministic constructions in real-world monitoring and synthesis.
Jane: It’s a roadmap then, showing us exactly which parts of this logic are easy to handle deterministically and which parts require those more powerful verification techniques.
Conclusion: Tom: So we’re wrapping up this look at "A General Automata Model for First-Order Temporal Logics (Extended Version)," and what we’re seeing is a framework that connects first-order logic directly to a new class of automata for temporal systems.
Jane: Basically, the paper shows how you can take complicated temporal requirements from first-order logic and map them onto these structured automata, which lets you check if those requirements are possible.
Tom: It’s a big step because it proves this new model can capture any first-order temporal logic over any signature and theory we choose.
Jane: That means the expressive power is massive; it’s not locked into just simple time sequences anymore, but it can handle the full complexity of first-order theories.
Lu: I think what really matters is that they showed how to encode almost anything—from symbolic finite automata to data-aware processes modulo theories—into this structure. That’s a huge representation learning idea here.
Meng: From an engineering standpoint, it's interesting how they show the translation from monadic first-order automata into equivalent finite-control ones using that specific theorem, because that simplifies things when we try to deploy these things in production.
Lalam: I’m confident in this direction. The self-contained proof for monodic first-order logic on finite words is a solid piece of evidence that this whole formalism works as intended.
Tom: It means for people building monitoring systems, they have a blueprint now to use these deterministic automata to build reactive synthesis tools without needing massive, undefined state spaces.
Jane: So the implication is that we can start designing systems where the temporal constraints are directly encoded into a structure that’s solvable using first-order logic rules.
Lu: The authors also laid out exactly where they are going next, suggesting lifting these first-order automata to infinite words, which is where they think the real challenge lies in rebuilding omega-regular language theory.
Meng: And for us shipping models, the focus has to be on those deterministic constructions from pure-past formulas because that’s what gives us a manageable size without needing that extra determinization step.
Lalam: I'm sure they're right; the connection to reactive synthesis and monitoring in the infinite-state setting is where this paper finds its most immediate practical use.
Tom: So, to wrap up, "A General Automata Model for First-Order Temporal Logics (Extended Version)" gives us a robust way to reason about FOLTL using first-order automata, with concrete results on decidability and efficiency for specific fragments.
Jane: It’s a solid foundation for anyone trying to verify complex system behaviors under temporal constraints.
Tom: And next time, we’re going to look at some of those other papers we have on the table, especially how they handle things like integer programming or verification in infinite-state networks.
University of Udine · INESC-ID / Instituto Superior Técnico, Universidade de Lisboa · Free University of Bozen-Bolzano
cs.LO
Submitted: 2024-05-30
Updated: 2026-11-10
Journal ref: Luca Geatti, Alessandro Gianola, Nicola Gigante. First-Order Automata. Proceedings of AAAI 2025: 14940-14948
DOI: 10.1609/AAAI.V39I14.33638
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 77/100
The gist: First-order automata are defined as a model capable of capturing first-order temporal logic on finite words…
Key concepts
- First-Order Automata
- These are automata designed to handle first-order logic over sequences of time points (first-order words). They allow capturing complex temporal logic formulas across any signature and theory, making them powerful tools for formal verification.
- FOLTL
- First-Order Temporal Logic on finite words is a type of logic that combines first-order quantification with temporal operators like X (next), U (until), and S (successor). The paper shows how these automata can interpret and satisfy these complex formulas over finite word structures.
- Non-emptiness Problem
- This problem asks whether a given first-order automaton accepts any word at all. The paper provides conditions under which this problem is semidecidable, offering practical ways to determine if a formula has any satisfying instances.
Terminology
Summary
First-order automata are defined as a model capable of capturing first-order temporal logic on finite words, showing how they can capture any FOLTL formula over any signature and theory The paper introduces this new class of automata and the corresponding notion of regular first-order languages, demonstrating their closure under common language-theoretic operations It shows how these automata can encode any FOLTL sentence over any first-order theory and provides conditions for the semidecidability of their non-emptiness problem Ultimately, the formalism is shown to be useful by proving the decidability of monodic FOLTL on finite words. p. 0
Pruning redundant reasoning tokens
The paper defines first-order words as sequences of T-structures where rigid symbols have constant interpretations throughout the word It then defines FOLTL formulas using a syntax involving terms, predicates, and temporal operators like X, Y, U, and S The semantics for satisfaction is detailed by defining how formulas are interpreted over non-empty first-order words based on time points in the word A FOLTL sentence is satisfiable if its T-language LT(φ) is not empty.
How the training signal is built
The authors introduce a symbolic representation for infinite state spaces using first-order logic, defining a first-order automaton A = hΣ, Γ, φ0, φT, φF i The automaton induces runs (sequences of states) when reading a T-word The acceptance condition is defined as a standard reachability condition based on the final state condition φF i.
Where the gains come from
The paper establishes several key results regarding the expressive power and decidability of these automata
-
First-order regular languages are closed under union and intersection. p. 2
-
T-regular languages are closed under concatenation and Kleene star, although this requires the use of second-order logic for a full proof. p. 0
-
Pure-past FOLTL sentences result in deterministic first-order automata, which is crucial for reactive synthesis and monitoring. p. 1
-
Monodic FOLTL on finite words is decidable, providing a self-contained proof of this classic result. p. 1
Decidability and Practical Implications
The paper addresses the non-emptiness problem for first-order automata by providing sufficient conditions for its semidecidability Specifically, Algorithm 1 provides a semi-decision procedure for automaton non-emptiness under certain conditions on the initial and final conditions. Furthermore, decidability can be recovered by restricting the state signature to finite-control or monadic automata. p. 6 The construction of deterministic first-order automata from pure-past FOLTL formulas is presented as the first step in designing a practical approach for reactive synthesis and monitoring. p. 5 The encoding of data-aware processes modulo theories (DMTs) into data-control automata is also shown, suggesting potential decidability criteria similar to those used for DMTs. p. 7
Model Encoding and Extensions
The paper details the translation from FOLTL to automata through a process involving the stepped normal form snf(φ) and surrogates XS, YS, ZS Encoding 1 formally defines A(φ) based on this structure The construction of monadic to finite-control automata via Encoding 3 demonstrates that any monadic automaton can be translated into an equivalent finite-control one, which is essential for proving Proposition 4 regarding the decidability of monodic FOLTL. The encoding of symbolic finite automata (s-FA) into first-order automata shows how these models can be represented using a single non-rigid constant and predicates corresponding to transition rules. p. 7 The encoding of DMTs into data-control automata uses constants for data variables and propositions for constraints, leading to Theorem 12 showing that a T-run of the DMT is also a T-run of its encoding. p. 7
Discussion and Future Directions
The paper concludes by comparing first-order automata to other infinite-state models like timed automata, hybrid automata, and Petri nets First-order automata are highlighted as a valuable tool for reasoning about FOLTL due to their direct connection to decidability results in restricted fragments. The authors suggest that lifting first-order automata to infinite words is the natural next step, although this presents significant challenges related to rebuilding the theory of omega-regular languages. p. 9 They also discuss promising paths for model checking using SMT technology and property-directed reachability techniques. p. 8 The construction of deterministic automata from pure-past FOLTL formulas is emphasized as a key component for reactive synthesis and monitoring in the infinite-state setting. p. 6
References
Alur, R., and Dill, D. p. 8 L. 1994. A theory of timed automata
Alur, R., and Madhusudan, P. p. 8 2004. Visibly pushdown languages
Alur, R.; Courcoubetis, C. p. 9; Henzinger, T. p. 9 p. 9 A.; and Ho, P. 1992. Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems
Alur, R.; Benedikt, M. p. 9; Etessami, K. p. 9; Godefroid, P. p. 9; Reps, T. W.; and Yannakakis, M. p. 9 2005. Analysis of recursive state machines
Artale, A., Geatti, L. p. 0 p. 0, Gigante, N. p. 0 p. 0, Mazzullo, A. p. 9 p. 9, and Montanari, A. p. 6 p. 6 p. 6 p. 6 2023a. Complexity of safety and cosafety fragments of linear temporal logic
Artale, A., Geatti, L., Gigante, N., Mazzullo, A., and Montanari, A. 2023b. Complexity of safety and cosafety fragments of Linear Temporal Logic
Barrett, C. W.; Sebastiani, R. p. 9; Seshia, S. p. 9 A.; and Tinelli, C. p. 9 2021. Satisfiability modulo theories
Benerecetti, M., Minopoli, S. p. 8, and Peron, A. p. 8 2010. Analysis of timed recursive state machines
Biere, A.; Cimatti, A. p. 9; Clarke, E. p. 0 M.; Strichman, O. p. 9; and Zhu, Y. p. 9 2009. Bounded model checking
Bradley, A. R. 2012. Understanding IC3
B¨uchi, J. R. 1962. On a decision method in restricted second order arithmetic
Calvanese, D.; Ghilardi, S. p. 8 p. 8; Gianola, A. p. 0 p. 0 p. 0 p. 0; Montali, M. p. 5 p. 5 p. 5, and Rivkin, A. p. 5 p. 5 p. 5 2021. Model completeness, uniform interpolants and superposition calculus
Calvanese, D.; Ghilardi, S.; Gianola, A.; Montali, M., and Rivkin, A. 2022. Combination of uniform interpolants via Beth definability
Chang, C. C., and Keisler, H. p. 7 J. 1992. Model theory, Third Edition
Clarke, E. M.; Grumberg, O. p. 9 p. 9; Jha, S.; Lu, Y.; and Veith, H. p. 9 2000. Counterexample-guided abstraction refinement
Clarke, E. M.; Grumberg, O.; Kroening, D. p. 9, Peled, D. p. 9 A., and Veith, H. p. 9 2018. Model checking, 2nd Edition
D’Antoni, L., and Veanes, M. p. 7 p. 7 p. 7 2014. Minimization of symbolic automata
D’Antoni, L., and Veanes, M. 2017. The power of symbolic automata and transducers
D’Antoni, L.; Kincaid, Z. p. 7; and Wang, F. p. 7 2018. A symbolic decision procedure for symbolic alternating finite automata
De Giacomo, G., and Vardi, M. p. 0 Y. 2013. Linear temporal logic and linear dynamic logic on finite traces
De Giacomo, G.; Di Stasio, A. p. 9; Fuggitti, F. p. 9; and Rubin, S. p. 9 2021. Pure-past linear temporal and dynamic logic on finite traces
Deutsch, A., Li, Y., and Vianu, V. p. 8 2019. Verification of hierarchical artifact systems
Droste, M.; D ¨uck, S.; Mandrioli, D.; and Pradella, M. 2017. Weighted operator precedence languages
Felli, P., Montali, M. p. 5 p. 5 p. 5, and Winkler, S. p. 7 p. 7 p. 7 p. 7 2022. Linear-time verification of data-aware dynamic systems with arithmetic
Gabbay, D.; Kurucz, A.; Wolter, F.; and Zakharyaschev, M. 2003. Fragments of first-order temporal logics
Gabbay, D. M., Schmidt, R. p. 8 A., and Szalas, A. p. 8 2008. Second-Order Quantifier Elimination - Foundations, Computational Aspects and Applications
Geatti, L.; Gianola, A.; Gigante, N. p. 0 p. 0 p. 0, and Winkler, S. 2023. Decidable fragments of ltlf modulo theories
Geatti, L.; Gigante, N., and Montanari, A. 2019. A SATbased encoding of the one-pass and tree-shaped tableau system for LTL
Geatti, L.; Gigante, N., and Montanari, A. 2021. BLACK: A fast, flexible and reliable LTL satisfiability checker
Ghilardi, S.; Gianola, A.; Montali, M., and Rivkin, A. 2023. Safety verification and universal invariants for relational action bases
Gianola, A., Montali, M., and Winkler, S. 2023. Lineartime verification of data-aware processes modulo theories via covers and automata (extended version)
Gianola, A., Montali, M., and Winkler, S. 2024. Lineartime verification of data-aware processes modulo theories via covers and automata
Gurfinkel, A., and Bjørner, N. p. 8 p. 8 S. 2019. The science, art, and magic of constrained horn clauses
Iosif, R., and Xu, X. 2019. Alternating automata modulo first order theories
Jacobs, S.; Bloem, R.; Brenguier, R.; Ehlers, R.; Hell, T., K ¨onighofer, R., Perez, G. A., Raskin, J.-F., Ryzhyk, L., Sankur, O., et al. 2017. The first reactive synthesis competition (syntcomp 2014)
Jensen, K., and Kristensen, L. p. 8 M. 2009. Coloured Petri Nets - Modelling and Validation of Concurrent Systems
Kaminski, M., and Francez, N. p. 8 1994. Finite-memory automata
Kontchakov, R.; Lutz, C.; Wolter, F., and Zakharyaschev, M. 2004. Temporalising tableaux
Leucker, M., and Schallhart, C. p. 0 p. 0 2009a. A brief account of runtime verification
Leucker, M., and Schallhart, C. 2009b. A brief account of runtime verification
Lichtenstein, O., Pnueli, A. p. 0, and Zuck, L. p. 5 1985. The glory of the past
Loeckx, J., and Sieber, K. p. 0 1987. The Foundations of Program Verification
Maler, O., and Nickovic, D. p. 6 2004. Monitoring temporal properties of continuous signals
McMillan, K. L., and Clarke, E. p. 0 M.; Henzinger, T. A.; Veith, H. p. 9, and Bloem, R., eds., Handbook of Model Checking
Murata, T. 1989. Petri nets: Properties, analysis and applications
Nenzi, L.; Bortolussi, L.; Ciancia, V.; Loreti, M., and Massink, M. 2015. Qualitative and quantitative monitoring of spatio-temporal properties
Pnueli, A., and Rosner, R. p. 0 1989. On the synthesis of an asynchronous reactive module
Pnueli, A. 1977. The temporal logic of programs
Rodr´ıguez, A., and S´anchez, C. p. 5 2023. Boolean abstractions for realizability modulo theories
Segoufin, L. 2006. Automata and logics for words and trees over an infinite alphabet
Tamm, H., and Veanes, M. 2018. Theoretical aspects of symbolic automata
Vardi, M. Y. 1991. Verification of concurrent programs: The automata-theoretic framework
Vardi, M. Y. 2005. An automata-theoretic approach to linear temporal logic
Veanes, M.; Hooimeijer, P.; Livshits, B.; Molnar, D., and Bjørner, N. S. 2012. Symbolic finite state transducers: algorithms and applications
Wojna, A. 1999. Counter machines
--- Page 1 ---
A General Automata Model for First-Order Temporal Logics (Extended Version) is a general class of automata capable of capturing first-order temporal logic on finite words, showing how they can capture any FOLTL formula over any signature and theory It shows how these automata can encode any FOLTL sentence over any first-order theory and provides sufficient conditions for the semidecidability of their non-emptiness problem Ultimately, the formalism is shown to be useful by proving the decidability of monodic FOLTL on finite words.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Model checking for Linear Temporal Logic with Past (LTL+P) can be performed by building a deterministic automaton from a pure-past FOLTL formula, which is then used to solve fixpoint computations for the winning region, making the reactive synthesis problem EXPTIMEcomplete rather than 2EXPTIMEcomplete.
-
Runtime verification systems can monitor properties expressed by temporal formulas by building a deterministic automaton equivalent to the starting temporal formula and checking whether it reaches a final state from which only final states are reachable.
-
Reactive synthesis for pure-past LTL+P fragments can be performed with a deterministic finite automaton of singly exponential size without needing a subsequent determinization step, achieving EXPTIMEcomplete complexity instead of 2EXPTIMEcomplete.
-
Monitoring in the infinite-state setting can leverage the construction of deterministic automata from pure-past fragments as a key component for runtime verification by checking reachability to final states.
-
Decidability results for emptiness problems can be recovered in specific restricted cases, such as finite-control automata, where emptiness is decidable based on testing if JAKk is T0 to k-satisfiable.
-
For monadic first-order automata, the decidability of monodic FOLTL sentences can be shown by translating the automaton into an equivalent finite-control automaton using Theorem 9.
-
Data-aware processes modulo theories (DMTs) can be modeled via data-control first-order automata where data variables in V define a signature Γ containing only constants, and constraints T r are encoded as transitions involving these constants.
Sources
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring