Concept
Linear temporal logic to Büchi automaton
Overview
In formal verification (a methodology from computer science), finite state model checking needs to find a Büchi automaton (BA) equivalent to a given linear temporal logic (LTL) formula, i.e., such that the LTL formula and the BA recognize the same ω-language. There are algorithms that translate an LTL formula to a BA. This transformation is normally done in two steps. The first step produces a generalized Büchi automaton (GBA) from a LTL formula. The second step translates this GBA into a BA, which involves a relatively easy construction. Since LTL is strictly less expressive than BA, the reverse construction is not always possible.
The algorithms for transforming LTL to GBA differ in their construction strategies but they all have a common underlying principle, i.e., each state in the constructed automaton represents a set of LTL formulas that are expected to be satisfied by the remaining input word after occurrence of the state during a run.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
The chief business of the logician is to classify arguments; for all testing clearly depends on classification. The classes of the logicians are defined by certain typical forms called syllogisms. For example, the syllogism called _Barbara_ is as follows: S is M; M is P: Hence, S is P. Or, to put words for letters— Enoch and Elijah were men; all men die: Hence, Enoch and Elijah must have died. The “is P” of the…
Charles S. Peirce, Chance, Love, and Logic
States what Linear temporal logic to Büchi automaton is.
In respect to any complex eternal object, _S(D1, D2, ... Dn)_, the eternal objects _D1, ... Dn_, whose individual essences are constitutive of the individual essence of _S(D1, ... Dn)_, are called the components of _S(D1, ... Dn)_. It is obvious that the grade of complexity to be ascribed to _S(D1, ... Dn)_ is to be taken as one above the highest grade of complexity to be found among its components.
Alfred North Whitehead, Science and the modern world
States what Linear temporal logic to Büchi automaton is.
Thought in such circumstances means no more than an act of abstraction or of formal identity. That is the sense in which thought is understood by Locke and all empiricists. Cognition, it is often said, can never do more than separate the given concrete objects into their abstract elements, and then consider these elements in their isolation. It is, however, at once apparent that this turns things upside down, and…
Georg Wilhelm Friedrich Hegel, The Logic of Hegel
States what Linear temporal logic to Büchi automaton is.
Related ideas
Place in the tradition
Part of Outline of logic.
Explore Linear temporal logic to Büchi automaton in the interactive graph →