Temporal logic and semidirect products: An effective characterization of the until hierarchy
We reveal an intimate connection between semidirect products of finite semigroups and substitution of formulas in linear temporal logic. e use this connection to obtain an algebraic characterization of the until hierarchy of linear temporal logic. (The kth level of that hierarchy is comprised of all temporal properties that are expressible by a formula of nesting depth k in the until operator.) Applying deep results from finite semigroup theory we are able to prove that each level of the until hierarchy is decidable. By means of Ehrenfeucht-Fraisse games, we extend the results from linear temporal logic over finite sequences to linear temporal logic over in finite sequences.
semidirect products until hierarchy finite semigroups substitution linear temporal logic pseudovarieties of semigroups aperiodic semigroups