✦ LIBER ✦

Min-max Computation Tree Logic

✍ Scribed by Pallab Dasgupta; P.P. Chakrabarti; Jatindra Kumar Deka; Sriram Sankaranarayanan

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 342 KB
Volume: 127
Category: Article
ISSN: 0004-3702
DOI: 10.1016/s0004-3702(01)00059-5

No coin nor oath required. For personal study only.

✦ Synopsis

This paper introduces a branching time temporal query language called Min-max CTL which is similar in syntax to the popular temporal logic, CTL [Clarke et al., ACM Trans. Program. Lang. Systems 8 (1986) 244]. However unlike CTL, Min-max CTL can express timing queries on a timed model. We show that interesting timing queries involving a combination of min and max can be expressed in Min-max CTL. While model checking using most timed temporal logics is PSPACEcomplete or harder [Alur and Henzinger, Inform. and Comput. 104 (1993) 35; Alur et al., Inform. and Comput. 104 (1993) 2], we show that many practical timing queries, where we are interested in the worst-case or best-case timings, can be answered in polynomial time by querying the system using Min-max CTL.

📜 SIMILAR VOLUMES

Quantified Computation Tree Logic

✍ A.C. Patthak; I. Bhattacharya; A. Dasgupta; Pallab Dasgupta; P.P. Chakrabarti 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Computation Tree Logic (CTL) is one of the most syntactically elegant and computationally attractive temporal logics for branching time model checking. In this paper, we observe that while CTL can be verified in time polynomial in the size of the state space times the length of the formula, there is

Paraconsistent Computation Tree Logic

✍ Ken Kaneiwa; Norihiro Kamide 📂 Article 📅 2011 🏛 Springer 🌐 English ⚖ 322 KB

Min–max tree covers of graphs

✍ G. Even; N. Garg; J. Könemann; R. Ravi; A. Sinha 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 225 KB

Approximation Algorithms for Min–Max Tre

Approximation Algorithms for Min–Max Tree Partition

✍ Nili Guttmann-Beck; Refael Hassin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 298 KB

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ž 2 . error ratio can be given for the problem unless P s NP.

Game tree searching by min/max approxima

Game tree searching by min/max approximation

✍ Ronald L. Rivest 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 931 KB

Approximation hardness of min–max tree c

Approximation hardness of min–max tree covers

✍ Zhou Xu; Qi Wen 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 367 KB

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees.