Edmund M. Clarke Jr. (auth.), Wojciech Penczek, Andrzej Szałas (eds.)3540615504, 9783540615507
The volume presents 35 revised full papers selected from a total of 95 submissions together with 8 invited papers and 2 abstracts of invited talks. The papers included cover issues from the whole area of theoretical computer science, with a certain emphasis on mathematical and logical foundations. The 10 invited presentations are of particular value.
Table of contents :
Word level model checking….Pages 1-1
Code problems on traces….Pages 2-17
Models of DNA computation….Pages 18-36
Theory and practice of action semantics….Pages 37-61
Linear time temporal logics over Mazurkiewicz traces….Pages 62-92
Partial order reduction: Model-checking using representatives….Pages 93-112
Nonmonotonic rule systems: Forward chaining, constraints, and complexity….Pages 113-113
Mind the gap! Abstract versus concrete models of specifications….Pages 114-134
A sequent calculus for subtyping polymorphic types….Pages 135-155
Kolmogorov complexity: Recent research in Moscow….Pages 156-166
A modal logic for data analysis….Pages 167-179
From specifications to programs: A fork-algebraic approach to bridge the gap….Pages 180-191
Logic of predicates with explicit substitutions….Pages 192-205
On the query complexity of sets….Pages 206-217
A Lambda Calculus of incomplete objects….Pages 218-229
Bisimilarity problems requiring exponential time (Extended abstract)….Pages 230-241
Linear dynamic Kahn networks are deterministic….Pages 242-254
Shortest path problems with time constraints….Pages 255-266
Parallel Alternating-Direction Access Machine….Pages 267-278
Specification and verification of timed lazy systems….Pages 279-290
A class of information logics with a decidable validity problem….Pages 291-302
On the power of nonconservative PRAM….Pages 303-311
Self-similarity viewed as a local property via tile sets….Pages 312-323
Simulation of specification statements in Hoare logic….Pages 324-335
Equational properties of iteration in algebraically complete categories….Pages 336-347
On unconditional transfer….Pages 348-359
(poly(log log n ), poly(log log n ))—Restricted verifiers are unlikely to exist for languages in $$mathcal{N}mathcal{P}$$ *….Pages 360-371
Minimizing congestion of layouts for ATM networks with faulty links….Pages 372-381
Polynomial automaticity, context-free languages, and fixed points of morphisms (Extended abstract)….Pages 382-393
Causal testing….Pages 394-406
Construction of list homomorphisms by tupling and fusion….Pages 407-418
Probabilistic metric semantics for a simple language with recursion….Pages 419-430
Dynamic graphs….Pages 431-442
Equations on trees….Pages 443-456
On the equivalence problem for E-pattern languages….Pages 457-468
Specifying and verifying parametric processes….Pages 469-481
On saturation with flexible function symbols….Pages 482-493
Approximating good simultaneous Diophantine approximations is almost NP-hard….Pages 494-505
On the conjugation of Standard morphisms….Pages 506-516
A semantic matching algorithm: Analysis and implementation….Pages 517-528
Routing on triangles, tori and honeycombs….Pages 529-541
A uniform analysis of trie structures that store prefixing-keys with application to doubly-chained prefixing-tries….Pages 542-553
On fairness in terminating and reactive programs….Pages 554-565
Polynomial time samplable distributions….Pages 566-578
From static to dynamic abstract data-types….Pages 579-590
Reviews
There are no reviews yet.