C. P. Schnorr (auth.), Shimon Even, Oded Kariv (eds.)3540108432, 9783540108436
Table of contents :
Refined analysis and improvements on some factoring algorithms….Pages 1-15
Absolute primality of polynomials is decidable in random polynomial time in the number of variables….Pages 16-28
Area-time optimal VLSI networks for computing integer multiplication and Discrete Dourier Transform….Pages 29-40
Cost tradeoffs in graph embeddings, with applications….Pages 41-55
Minimum s-t cut of a planar undirected network in o(n log 2 (n)) time….Pages 56-67
On the density of color-families….Pages 68-72
The implication problem for data dependencies….Pages 73-85
Characterizing data base Dependencies….Pages 86-97
Data flow analysis of applicative programs….Pages 98-113
Flow analysis of lambda expressions….Pages 114-128
Algorithmic specifications of abstract data types….Pages 129-147
Nondeterminism in abstract data types….Pages 148-164
A view of directions in relational database theory….Pages 165-176
A new characterization of the regular languages….Pages 177-183
Langages Reconnaissables et Codage Prefixe Pur….Pages 184-192
Passes, sweeps and visits….Pages 193-207
On LALR(k) testing….Pages 208-217
On size bounds for deterministic parsers….Pages 218-228
A decision procedure for the equivalence of two dpdas one of which is linear….Pages 229-237
The deducibility problem in Propositional Dynamic Logic….Pages 238-248
Finite models for deterministic propositional dynamic logic….Pages 249-263
Impartiality, justice and fairness: The ethics of concurrent termination….Pages 264-277
Computing a perfect strategy for n×n chess requires time exponential in n….Pages 278-293
On the complexity of simple arithmetic expressions….Pages 294-304
Proving lower bounds for linear decision trees….Pages 305-315
Parikh-bounded languages….Pages 316-323
Generalized Parikh mappings and homomorphisms….Pages 324-332
Chomsky-Schotzenberger representations for families of languages and grammatical types….Pages 333-347
Algebraically specified programming systems and Hoare’s logic….Pages 348-362
Automatic construction of verification condition generators from hoare logics….Pages 363-377
Circular expressions: Elimination of static environments….Pages 378-392
An axiomatic approach to the Korenjak – Hopcroft algorithms….Pages 393-407
On the (generalized) post correspondence problem with lists of length 2….Pages 408-416
A sparse table implementation of priority queues….Pages 417-431
Comparing and putting together recursive path ordering, simplification orderings and Non-Ascending Property for termination proofs of term rewriting systems….Pages 432-447
Termination of linear rewriting systems….Pages 448-458
Realizing an equational specification….Pages 459-478
A cook’s tour of countable nondeterminism….Pages 479-494
The complexity of decision problems for finite-turn multicounter machines….Pages 495-505
Alternating multihead finite automata….Pages 506-520
The solution for the branching factor of the alpha-beta pruning algorithm….Pages 521-529
Uniform complexity and digital signatures….Pages 530-543
On the generation of cryptographically strong pseudo-random sequences….Pages 544-550
Measuring the expressive power of dynamic logics: An application of abstract model theory….Pages 551-551
Reviews
There are no reviews yet.