NDLI: Improved upper and lower bounds for modal logics of programs

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

A simple parallel algorithm for the maximal independent set problem

The two-processor scheduling problem is in R-NC

Constructing a perfect matching is in random NC

A parallel algorithm for the maximal path problem

The parallel complexity of exponentiating polynomials over finite fields

One, two, three . . . infinity: lower bounds for parallel computation

Tradeoffs for VLSI models with subpolynomial delay

Algorithms for routing and testing routability of planar VLSI layouts

Provably good routing in graphs: regular arrays

Expanders obtained from affine transformations

Expanders, sorting in rounds and superconcentrators of limited depth

White pebbles help

Stable prehension with three fingers

Riemann hypothesis and finding roots over finite fields

Computing with polynomials given by straight-line programs I: greatest common divisors

Efficient parallel solution of linear systems

Polynomial time solutions of some problems of computational algebra

A general approach to d-dimensional geometric queries

Space-time tradeoffs for orthogonal range queries

A probabilistic algorithm for the post office problem

A linear algorithm for finding dominators in flow graphs and related problems

Multicommodity flows in planar undirected graphs and shortest paths

The effect of updates in binary search trees

Finding the median requires 2n comparisons

Self-organizing sequential search and Hilbert's inequalities

On the expected behavior of disjoint set union algorithms

Concurrent dynamic logic

Improved upper and lower bounds for modal logics of programs

Transition systems, infinitary languages and the semantics of uniform concurrency

Provable isomorphisms and domain equations in models of typed languages

Equational theories and database constraints

The polynomial hierarchy and fragments of bounded arithmetic

The knowledge complexity of interactive proof-systems

An internal semantics for modal logic

An O(lg n) expected rounds randomized Byzantine generals protocol

Fault tolerance of minimal path routings in a network

The distributed firing squad problem

Optimal precision in the presence of uncertainty

The cryptographic security of truncated linearly related variables

One-way functions and pseudorandom generators

Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources

On the stability of the Ethernet

A simple three-dimensional real-time cellular array

Doubly lexical orderings of matrices

The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems

Fast algorithms for n-dimensional restrictions of hard problems

Trading group theory for randomness

An algorithm for finding Hamilton cycles in random graphs

Compression and ranking

The complexity of backtrack searches

NP is as easy as detecting unique solutions

Are search and decision programs computationally equivalent?

Dual integer linear programs and the relationship between their optima

Improved upper and lower bounds for modal logics of programs

Content Provider	ACM Digital Library
Author	Stockmeyer, L Vardi, M Y
Abstract	We describe novel techniques for establishing improved upper and lower bounds for modal logics of programs: 1) We introduce hybrid tree automata. These automata seems to be doubly exponential more powerful than Rabin tree automata but their emptiness problem is only exponentially harder (nondeterministic exponential time vs. nondeterministic polynomial time). The satisfiability problem for several logics is reducible to the emptiness problem for hybrid tree automata. Using this reduction we show that the satisfiability problems for Streett's delta-PDL. Kozen's μ-calculus and Parikh's game logic are solvable in nondeterministic exponential time, and the satisfiability problem for Emerson and Halpern's CTL and Vardi and Wolper's process logic (YAPL) are solvable in nondeterministic doubly exponential time. 2) We encode Turing machine computations by Kripke structures where every state in the structure represents a single tape cell. This yields a deterministic doubly exponential time lower bound for CTL and YAPL. 3) For variants of CTL and YAPL that deal only with finite computations we prove completeness for deterministic doubly exponential time.
Starting Page	240
Ending Page	251
Page Count	12
File Format	PDF
ISBN	0897911512
DOI	10.1145/22145.22173
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1985-12-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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