On the Hybrid Extension of CTL and CTL - Computer Science > Logic in Computer ScienceReportar como inadecuado




On the Hybrid Extension of CTL and CTL - Computer Science > Logic in Computer Science - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The paper studies the expressivity, relative succinctness and complexity ofsatisfiability for hybrid extensions of the branching-time logics CTL and CTL+by variables. Previous complexity results show that only fragments with onevariable do have elementary complexity. It is shown that H1CTL+ and H1CTL, thehybrid extensions with one variable of CTL+ and CTL, respectively, areexpressively equivalent but H1CTL+ is exponentially more succinct than H1CTL.On the other hand, HCTL+, the hybrid extension of CTL with arbitrarily manyvariables does not capture CTL*, as it even cannot express the simple CTL*property EGFp. The satisfiability problem for H1CTL+ is complete for triplyexponential time, this remains true for quite weak fragments and quite strongextensions of the logic.



Autor: Ahmet Kara, Martin Lange, Thomas Schwentick, Volker Weber

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados