NDLI: Graded computation tree logic

Please wait, while we are loading the content...

ACM Transactions on Computational Logic (TOCL) : Volume 17

ACM Transactions on Computational Logic (TOCL) : Volume 16

ACM Transactions on Computational Logic (TOCL) : Volume 15

ACM Transactions on Computational Logic (TOCL) : Volume 14

ACM Transactions on Computational Logic (TOCL) : Volume 13

Issue 4, October 2012

Issue 3, August 2012

The dynamic complexity of formal languages

Permissive-nominal logic: First-order logic over nominal terms and sets

LTL over description logic axioms

Calculus of cooperation and game-based reasoning about protocol privacy

Deductive inference for the interiors and exteriors of horn theories

Arithmetic complexity via effective names for random sequences

Graded computation tree logic

Well-structured program equivalence is highly undecidable

Algorithmic analysis of array-accessing programs

Issue 2, April 2012

Issue 1, January 2012

ACM Transactions on Computational Logic (TOCL) : Volume 12

ACM Transactions on Computational Logic (TOCL) : Volume 11

ACM Transactions on Computational Logic (TOCL) : Volume 10

ACM Transactions on Computational Logic (TOCL) : Volume 9

ACM Transactions on Computational Logic (TOCL) : Volume 8

ACM Transactions on Computational Logic (TOCL) : Volume 7

ACM Transactions on Computational Logic (TOCL) : Volume 6

ACM Transactions on Computational Logic (TOCL) : Volume 5

ACM Transactions on Computational Logic (TOCL) : Volume 4

ACM Transactions on Computational Logic (TOCL) : Volume 3

ACM Transactions on Computational Logic (TOCL) : Volume 2

ACM Transactions on Computational Logic (TOCL) : Volume 1

Graded computation tree logic

Content Provider	ACM Digital Library
Author	Murano, Aniello Mogavero, Fabio Bianco, Alessandro
Copyright Year	2012
Abstract	In modal logics, graded (world) modalities have been deeply investigated as a useful framework for generalizing standard existential and universal modalities in such a way that they can express statements about a given number of immediately accessible worlds. These modalities have been recently investigated with respect to the μCalculus, which have provided succinctness, without affecting the satisfiability of the extended logic, that is, it remains solvable in ExpTime. A natural question that arises is how logics that allow reasoning about paths could be affected by considering graded path modalities. In this article, we investigate this question in the case of the branching-time temporal logic CTL (GCTL, for short). We prove that, although GCTL is more expressive than CTL, the satisfiability problem for GCTL remains solvable in ExpTime, even in the case that the graded numbers are coded in binary. This result is obtained by exploiting an automata-theoretic approach, which involves a model of alternating automata with satellites. The satisfiability result turns out to be even more interesting as we show that GCTL is at least exponentially more succinct than graded μCalculus.
Starting Page	1
Ending Page	53
Page Count	53
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/2287718.2287725
Volume Number	13
Issue Number	3
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-08-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Branching temporal logics Graded modalities Satisfiability Specification
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Logic Computational Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Graded Computation Tree Logic

Undecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting

Optimal Tableau Method for Constructive Satisfiability Testing and Model Synthesis in the Alternating-Time Temporal Logic $ATL^{+}$

Temporal logics for real-time system specification

Robust Vacuity for Branching Temporal Logic

Comments on temporal logics for real-time system specification

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

Graded Computation Tree Logic (2008)

Two-Variable Logic with Counting and Trees

Graded computation tree logic

Similar Documents

Graded Computation Tree Logic

Undecidable Propositional Bimodal Logics and One-Variable First-Order Linear Temporal Logics with Counting

Optimal Tableau Method for Constructive Satisfiability Testing and Model Synthesis in the Alternating-Time Temporal Logic $ATL^{+}$

Temporal logics for real-time system specification

Robust Vacuity for Branching Temporal Logic

Comments on temporal logics for real-time system specification

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

Graded Computation Tree Logic (2008)

Two-Variable Logic with Counting and Trees

Graded computation tree logic