QEMTLFeb2011-1.pdf (346.76 kB)

Monodic temporal logic with quantified propositional variables

Download (346.76 kB)
journal contribution
posted on 13.06.2014, 07:59 by Walter Hussak
We extend the monodic fragment of first-order linear temporal logic to include right-linear grammar operators and quantification of propositional variables. Unlike propositional temporal logic, the use of grammar operators in first-order temporal logic is not equivalent to general propositional quantification, as the latter admit satisfiable formulae without countable models. We consider the decision problem for fragments where propositional quantification occurs outside of quantification of individual variables and temporal (grammar) operators. We show that if externally quantified propositions inside temporal operators occur within positive occurrences of universal quantifiers for individual variables, then validity for all propositional prefix classes is recursively enumerable and decidable in the two-variable case. Without this condition we show that, even with very severe restrictions on the first-order part of the logic, no non-trivial prefix class is recursively enumerable.

History

School

  • Science

Department

  • Computer Science

Published in

JOURNAL OF LOGIC AND COMPUTATION

Volume

22

Issue

3

Pages

517 - 544 (28)

Citation

HUSSAK, W., 2012. Monodic temporal logic with quantified propositional variables. Journal of Logic and Computation, 22 (3), pp. 517 - 544.

Publisher

© The Author. Published by Oxford University Press

Version

AM (Accepted Manuscript)

Publication date

2012

Notes

This article was published in the Journal of Logic and Computation [© The Author. Published by Oxford University Press] and the definitive version is available at: http://dx.doi.org/10.1093/logcom/exr004

ISSN

0955-792X

Language

en

Exports