Micah Adler, John W. Byers, Richard M. Karp (auth.), Jiří Wiedermann, Petr Hájek (eds.)3540602461, 9783540602460
The book contains eight invited papers and two abstracts of invited talks by outstanding scientists as well as 44 revised full research papers selected from a total of 104 submissions. All relevant aspects of theoretical computer science are addressed, particularly the mathematical foundations; the papers are organized in sections on structural complexity, algorithms, complexity theory, graphs in models of computation, lower bounds, formal languages, unification, rewriting and type theory, distributed computation, concurrency, semantics, model checking, and formal calculi.
Table of contents :
Scheduling parallel communication: The h -relation problem….Pages 1-20
Decomposable structures, Boolean function representations, and optimization….Pages 21-36
The complexity of interval routing on random graphs….Pages 37-49
Bridging across the log(n) space frontier….Pages 50-65
Second order logic and the weak exponential hierarchies….Pages 66-81
On the computing paradigm and computational complexity….Pages 82-92
Ranked structures in nonmonotonic reasoning and belief revision: Abstract….Pages 93-93
Symbolic dynamics and finite automata….Pages 94-104
Lower bounds for propositional proofs and independence results in bounded arithmetic (abstract)….Pages 105-105
Physics and the new computation….Pages 106-128
Measure on P: Robustness of the notion….Pages 129-138
Comparing counting classes for logspace, one-way logspace, and first-order….Pages 139-148
Automata that take advice….Pages 149-158
Nonuniform lower bounds for exponential time classes….Pages 159-168
On a quantitative notion of uniformity….Pages 169-178
Separations by random oracles and “Almost” classes for generalized reducibilities….Pages 179-190
On the complexity of finite memory policies for Markov decision processes….Pages 191-200
Derandomization for sparse approximations and independent sets….Pages 201-210
Asymptotically efficient in-place merging….Pages 211-220
The complexity of the falsifiability problem for pure implicational formulas….Pages 221-226
Strong lower bounds on the approximability of some NPO PB-complete maximization problems….Pages 227-236
Some typical properties of large AND/OR Boolean formulas….Pages 237-246
The hedge: An efficient storage device for Turing machines with one head….Pages 247-256
Graph inference from a walk for trees of bounded degree 3 is NP-complete….Pages 257-266
Honeycomb networks….Pages 267-276
Witness-isomorphic reductions and the local search problem (extended abstract)….Pages 277-287
Multiple product modulo arbitrary numbers….Pages 288-298
Lower bounds for the majority communication complexity of various graph accessibility problems….Pages 299-308
Strong optimal lower bounds for Turing machines that accept nonregular languages….Pages 309-318
A superpolynomial lower bound for (1,+ k(n) )-branching programs….Pages 319-325
Deterministic parsing for augmented context-free grammars….Pages 326-336
A periodicity theorem on words and applications….Pages 337-348
A new approach to analyse Coupled-Context-Free languages….Pages 349-358
Computational complexity of simultaneous elementary matching problems….Pages 359-370
Graph reducibility of term rewriting systems….Pages 371-381
Positive recursive type assignment….Pages 382-391
String recognition on anonymous rings….Pages 392-401
The firing squad synchronization problem on Cayley graphs….Pages 402-411
Solving cheap graph problems on Meshes….Pages 412-422
An elementary bisimulation decision procedure for arbitrary context-free processes….Pages 423-433
On congruences and partial orders….Pages 434-443
Performance preorder: Ordering processes with respect to speed….Pages 444-453
Towards a semantic theory of CML….Pages 454-466
Modular constructions of distributing automata….Pages 467-478
On the proof method for bisimulation….Pages 479-488
Towards a calculus of predicate transformers….Pages 489-498
An abstract account of composition….Pages 499-508
Syntax and semantics of Procol….Pages 509-518
Synthesizing distinguishing formulae for real time systems -extended abstract….Pages 519-528
From timed automata to logic — and back….Pages 529-539
Incremental model checking for decomposable structures….Pages 540-551
Automata for the modal μ-calculus and related results….Pages 552-562
A ν-calculus with local views for systems of sequential agents….Pages 563-573
An operator calculus approach to the evolution of dynamic data structures….Pages 574-586
Reviews
There are no reviews yet.