Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Model Checking
Optimal Algorithm
System Modeling
Temporal Logic
Subscribe
Academic
Publications
Complexity results on branchingtime pushdown model checking
Complexity results on branchingtime pushdown model checking,10.1016/j.tcs.2007.03.049,Theoretical Computer Science,Laura Bozzelli
Edit
Complexity results on branchingtime pushdown model checking
(
Citations: 3
)
BibTex

RIS

RefWorks
Download
Laura Bozzelli
The
model checking
problem of pushdown systems (PMC problem, for short) against standard branching temporal logics has been intensively studied in the literature. In particular, for the modal μcalculus, the most powerful branching
temporal logic
used for verification, the problem is known to be Exptimecomplete (even for a fixed formula). The problem remains Exptimecomplete also for the logic CTL, which corresponds to a fragment of the alternationfree modal μcalculus. For the logic CTL∗, the problem is known to be in 2Exptime. In this paper, we show that the complexity of the PMC problem for CTL∗ is in fact 2Exptimecomplete. Moreover, we give a new
optimal algorithm
to solve this problem based on automata theoretic techniques. Finally, we prove that the program complexity of the PMC problem against CTL (i.e., the complexity of the problem in terms of the size of the system) is Exptimecomplete.
Journal:
Theoretical Computer Science  TCS
, vol. 379, no. 12, pp. 286297, 2007
DOI:
10.1016/j.tcs.2007.03.049
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
linkinghub.elsevier.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(1)
...Several modelchecking algorithms have been proposed for both lineartime logics [1,13,9,14,17], and branchingtime logics [1,
2
,6,24,18,19,14,17]...
...However, these algorithms either allow only to decide whether a given configuration satisfies the formula i.e., they cannot compute all the set of PDS configurations where the formula holds [5,6,24,18], or have a high complexity [19,
2
,1,12,11,14,17]...
...Our procedure is more e cient than the existing modelchecking algorithms for calculus and CTL* that are able to compute the set of configurations where a given property holds [19,
2
,1,12,11,14,17]...
...[
2
] considers the emptiness problem in Alternating Parity Pushdown Automata...
...Model checking CTL* for PDS is 2EXPTIMEcomplete (in the size of the formula) [
2
]...
...Algorithms for modelchecking CTL* specifications for PDSs have been proposed in [14,12,11,
2
]...
Fu Song
,
et al.
Efficient CTL ModelChecking for Pushdown Systems
References
(9)
Composition, Decomposition and Model Checking of Pushdown Processes
(
Citations: 40
)
Olaf Burkart
,
Bernhard Steffen
Journal:
Nordic Journal of Computing  NJC
, vol. 2, no. 2, pp. 89125, 1995
Automatic verification of finitestate concurrent systems using temporal logic specifications
(
Citations: 2037
)
Edmund Melson Clarke
,
E. Allen Emerson
,
A. Prasad Sistla
Published in 1986.
Using Branching Time Temporal Logic to Synthesize Synchronization Skeletons
(
Citations: 303
)
E. Allen Emerson
,
Edmund M. Clarke
Journal:
Science of Computer Programming  SCP
, vol. 2, no. 3, pp. 241266, 1982
Sometimes" and "Not Neve r" revisited: on branching versus linear time
(
Citations: 86
)
E. A. Emerson
,
J. Y. Halpern
Journal:
Journal of The ACM  JACM
, 1986
Model checking LTL with regular valuations for pushdown systems
(
Citations: 67
)
Javier Esparza
,
Antonín Kucera
,
Stefan Schwoon
Journal:
Information and Computation/information and Control  IANDC
, vol. 186, no. 2, pp. 355376, 2003
Sort by:
Citations
(3)
Branchingtime model checking of onecounter processes
(
Citations: 2
)
Stefan Göller
,
Markus Lohrey
Journal:
Computing Research Repository  CORR
, vol. abs/0909.1, pp. 405416, 2009
Software life cycle modelsindustrial implications
(
Citations: 1
)
V. Kadary
,
D. EvenTsur
,
N. Halperin
,
S. Koenig
Conference:
Israel Conference on Computer Systems and Software Engineering  ICCSSE
, 1989
Efficient CTL ModelChecking for Pushdown Systems
Fu Song
,
Tayssir Touili