STACS 86: 3rd Annual Symposium on Theoretical Aspects of Computer Science Orsay, France, January 16–18, 1986 [1 ed.] 9783540160786, 3540160787 [DJVU]

Table of contents :
Abstract interpretation of denotational definitions....Pages 1-20
Temporal reasoning under generalized fairness constraints....Pages 21-36
Decidabilite de l'egalite des Langages Algebriques Infinitaires Simples....Pages 37-48
Some probabilistic powerdomains in the category SFP....Pages 49-59
Ions and local definitions in logic programming....Pages 60-72
Input sensitive, optimal parallel randomized algorithms for addition and identification....Pages 73-86
A parallel statistical cooling algorithm....Pages 87-97
Subgraph isomorphism for biconnected outerplanar graphs in cubic time....Pages 98-103
Polynomial time algorithms for finding integer relations among real numbers....Pages 105-118
New upperbounds for decentralized extrema-finding in a ring of processors....Pages 119-129
Algorithms for visibility representations of planar graphs....Pages 130-141
Speeding up random access machines by few processors....Pages 142-152
Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs....Pages 153-170
On sparseness, ambiguity and other decision problems for acceptors and transducers....Pages 171-179
Varietes de Semis Groupes et Mots Infinis....Pages 180-191
Equations in free partially commutative monoids....Pages 192-202
Separating and testing....Pages 203-212
Decomposition de Fonctions Rationnelles....Pages 213-226
Long unavoidable patterns....Pages 227-235
Abstract implementations and correctness proofs....Pages 236-251
Strictness and serializability....Pages 252-261
Towards specification and proof of asynchronous systems....Pages 262-276
Monotone boolean formulas, distributive lattices, and the complexities of logics, algebraic structures, and computation structures (preliminary report)....Pages 277-290
Concurrent conciseness of degree, probabilistic, nondeterministic and deterministic finite automata....Pages 291-305
Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω -machines....Pages 306-320
On sparse oracles separating feasible complexity classes....Pages 321-333
On generalized kolmogorov complexity....Pages 334-340
Area-time optimal division for T =Ω(( logn ) 1+ε )....Pages 341-352
A time-space tradeoff for element distinctness....Pages 353-358
Parallel machines and their communication theoretical limits....Pages 359-368