Samson Abramsky (auth.), Igor Prívara, Peter Ružička (eds.)3540634371, 9783540634379
The 40 revised full papers presented were carefully selected from a total of 94 submissions. Also included are nine invited papers and two abstracts of invited talks. The papers cover the whole range of theoretical computer science including programming theory, complexity theory, mathematical logic, rewriting, grammars, formal languages, theory of algorithms, computational graph theory, etc.
Table of contents :
Game semantics for programming languages….Pages 1-4
Communication complexity….Pages 5-18
Treewidth: Algorithmic techniques and results….Pages 19-36
When are two rewrite systems more than none?….Pages 37-43
Positive applications of lattices to cryptography….Pages 44-51
A tile-based coordination view of asynchronous π-calculus….Pages 52-70
Communication complexity and sequential computation….Pages 71-84
Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus….Pages 85-90
Computational limitations of Stochastic Turing machines and Arthur-Merlin games with small space bounds….Pages 91-107
Learning to perform knowledge-intensive inferences….Pages 108-109
Resolution proofs, exponential bounds, and Kolmogorov complexity….Pages 110-116
The expressiveness of Datalog cicuits (DAC)….Pages 117-128
The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes….Pages 129-138
A category of transition systems and its relations with orthomodular posets….Pages 139-148
Accepting Zeno words without making time stand still….Pages 149-158
Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams….Pages 159-168
Specifying computations using hyper transition systems….Pages 169-178
A shift-invariant metric on S zz inducing a non-trivial topology….Pages 179-188
Subtyping calculus of construction (extended abstract)….Pages 189-198
Distances between languages and reflexivity of relations….Pages 199-208
Partial characterization of synchronization languages….Pages 209-218
Integrating the specification techniques of graph transformation and temporal logic….Pages 219-228
On the generation of trees by hyperedge replacement….Pages 229-238
Regulation by valences….Pages 239-248
Simulation as a correct transformation of rewrite systems….Pages 249-258
On the dilation of interval routing….Pages 259-268
Relating conflict-free stable transition and event models (extended abstract)….Pages 269-278
The giant component threshold for random regular graphs with edge faults….Pages 279-288
A topological generalization of propositional linear time temporal logic….Pages 289-297
Multi-head finite automata: Data-independent versus data-dependent computations….Pages 299-308
Complexity of finding short resolution proofs….Pages 309-318
On P versus NP∩co-NP for decision trees and read-once branching programs….Pages 319-326
A characterization of abstract families of algebraic power series….Pages 327-336
Repetitiveness of D0L-languages is decidable in polynomial time….Pages 337-346
Minimal letter frequency in n -th power-free binary words….Pages 347-357
Real-time generation of primes by a one-dimensional cellular automaton with 11 states….Pages 358-367
Optimal algorithms for complete linkage clustering in d dimensions….Pages 368-377
Invertible linear cellular automata over Z m : Algorithmic and dynamical aspects….Pages 378-387
Two-level contextual grammars: The internal case….Pages 388-397
Counting problems over the reals….Pages 398-407
On the influence of the state encoding on OBDD-representations of finite state machines….Pages 408-417
Decomposition of TrPTL formulas….Pages 418-427
NP-hard sets have many hard instances….Pages 428-437
Deciding verbose languages with linear advice….Pages 438-447
Homomorphic images of sentential forms and terminating grammars (extended abstract)….Pages 448-457
Simplification orders for term graph rewriting….Pages 458-467
Dependency-based action refinement….Pages 468-477
A hierarchy for (1, + k )-branching programs with respect to k ….Pages 478-487
Routing with finite speeds of memory and network….Pages 488-497
Queries and algorithms computable by polynomial time existential reflective machines….Pages 498-507
Partial order semantics and read arcs….Pages 508-517
Reviews
There are no reviews yet.