𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of the temporal logic with “until” over general linear time

✍ Scribed by M. Reynolds

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
350 KB
Volume
66
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that the decision problem for the temporal logic with the strict until operator over general linear time is PSPACE-complete. This shows that it is no harder to reason with arbitrary linear orderings than with discrete linear time temporal logics. New techniques are used to give a PSPACE procedure for the logic.

📜 SIMILAR VOLUMES

On the expressivity and complexity of qu
On the expressivity and complexity of quantitative branching-time temporal logics
✍ F. Laroussinie; Ph. Schnoebelen; M. Turuani 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 347 KB

We investigate extensions of CTL allowing to express quantitative requirements about an abstract notion of time in a simple discrete-time framework, and study the expressive power of several relevant logics. When only subscripted modalities are used, polynomial-time model checking is possible even

On the linear complexity of generalized
On the linear complexity of generalized cyclotomic sequences with the period
✍ Tongjiang Yan; Shengqiang Li; Guozhen Xiao 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 178 KB

This letter contributes to the investigation of the linear complexity of generalized cyclotomic sequences with the period p m , which are contained by the sequences constructed by C. Ding and T. Helleseth in 1998, as a representative special case. The results obtained confirm that all of these seque