Eric W. Allender (auth.), Laurent Kott (eds.)3540167617, 9783540167617
Table of contents :
Characterizations of PUNC and precomputation….Pages 1-10
Comparison of algorithms controlling concurrent access to a database: A combinatorial approach….Pages 11-20
A new duality result concerning Voronoi diagrams….Pages 21-30
Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial….Pages 31-39
On exponential lowness….Pages 40-49
A tradeoff between search and update time for the implicit dictionary problem….Pages 50-59
Intersections of some families of languages….Pages 60-68
Correspondence between ternary simulation and binary race analysis in gate networks….Pages 69-78
Counting with rational functions….Pages 79-88
Finite biprefix sets of paths in a Graph….Pages 89-94
Parallel RAMs with owned global memory and deterministic context-free language recognition….Pages 95-104
A Strong restriction of the inductive completion procedure….Pages 105-115
On discerning words by automata….Pages 116-122
Complexity classes without machines: On complete languages for UP….Pages 123-135
Containment, separation, complete sets, and immunity of complexity classes….Pages 136-145
On nontermination of Knuth-Bendix algorithm….Pages 146-156
Tradeoffs for language recognition on parallel computing models….Pages 157-166
Rational equivalence relations….Pages 167-176
Some further results on digital search trees….Pages 177-185
Knowledge, belief and time….Pages 186-195
A termination detector for static and dynamic distributed systems with asynchronous non-first-in-first-out communication….Pages 196-205
Decompositions of nondeterministic reductions….Pages 206-214
Hierarchical planarity testing algorithms….Pages 215-225
Synthesis and equivalence of concurrent systems….Pages 226-235
The set union problem with backtracking….Pages 236-243
Torsion matrix semigroups and recognizable transductions….Pages 244-253
On recognizable subsets of free partially commutative monoids….Pages 254-264
Min Cut is NP-complete for edge weighted trees….Pages 265-274
Alternating automata, the weak monadic theory of the tree, and its complexity….Pages 275-283
Subpolynomial complexity classes of real functions and real numbers….Pages 284-293
Etude syntaxique des parties reconnaissables de mots infinis….Pages 294-303
Refusal testing….Pages 304-313
A timed model for communicating sequential processes….Pages 314-323
A uniform reduction theorem extending a result of J. Grollmann and A. Selman….Pages 324-333
On the complexity of deciding fair termination of probabilistic concurrent finite-state programs….Pages 334-343
A new approach to detection of locally indicative stability….Pages 344-358
A more efficient algorithm for lattice basis reduction….Pages 359-369
Lower bounds by recursion theoretic arguments….Pages 370-375
An improved algorithm for transitive closure on acyclic digraphs….Pages 376-386
Un algorithme determinant les melanges de deux mots….Pages 387-396
A very fast, practical algorithm for finding a negative cycle in a digraph….Pages 397-406
A compositional reformulation of Owicki-Gries’s partial correctness logic for a concurrent while language….Pages 407-415
Semigroups and languages of dot-depth 2….Pages 416-423
A parallel vertex insertion algorithm for minimum spanning trees….Pages 424-433
More complicated questions about maxima and minima, and some closures of NP….Pages 434-443
Lower bounds for dynamic range query problems that permit subtraction (extended abstract)….Pages 444-453
E-unification algorithms for a class of confluent term rewriting systems….Pages 454-463
On fixed-point clones….Pages 464-473
Reviews
There are no reviews yet.