Succinctness gap between monadic logic and duration calculus

• Autorzy: Rabinovich A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

duration calculus; monadic logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2000
• Tom: Vol. 42, Nr 2
• Strony: 201--210
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Rabinovich A.

• Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel,