Quantitative Temporal Logics: {\sc PSpace} and below

C. LutzC. Lutz, D. WaltherD. Walther, F. WolterF. Wolter

$Quantitative Temporal Logics: {\sc PSpace} and below$

Download

C. Lutz, D. Walther, F. Wolter
Quantitative Temporal Logics: {\sc PSpace} and below
Proceedings of the Twelfth International Symposium on Temporal Representation and Reasoning, 2005. IEEE Computer Society Press

Details
Bibtex

KurzfassungAbstract
Often, the addition of metric operators to qualitative temporal
logics leads to an increase of the complexity of satisfiability by at least one exponential. In this paper, we exhibit a number of metric extensions of qualitative temporal logics of the real line that do not lead to an increase in computational complexity. We show that the language obtained by extending since/until logic of the real line with the operators `sometime within n time units', n coded in binary, is PSpace-complete even without the finite variability assumption. Without qualitative temporal operators the complexity of this language turns out to depend on whether binary or unary coding of parameters is assumed: it is still PSpace-hard under
binary coding but in NP under unary coding.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ LutzWaltherWolter-TIME-05,
  address = {Burlington, VT, USA},
  author = {C. {Lutz} and D. {Walther} and F. {Wolter}},
  booktitle = {Proceedings of the Twelfth International Symposium on Temporal Representation and Reasoning},
  publisher = {IEEE Computer Society Press},
  title = {Quantitative Temporal Logics: {\sc PSpace} and below},
  year = {2005},
}