Succinctness Gap between Monadic Logic and Duration Calculus

Article type: Research Article

Authors: Rabinovich, A.

Affiliations: Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. e.mail: rabino@math.tau.ac.il

Note: [] Address for correspondence: Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Abstract: In [8, 11] the expressive completeness of the Propositional fragment of Duration Calculus relative to monadic first-order logic of order was established. In this paper we show that there is at least an exponential blow-up in every meaning preserving translation from monadic logic to PDC. Hence, there exists an exponential gap between the succinctness of monadic logic and that of duration calculus.

DOI: 10.3233/FI-2000-42204

Journal: Fundamenta Informaticae, vol. 42, no. 2, pp. 201-210, 2000