STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992 Proceedings

Structuring and modularizing algebraic specifications: the PLUSS specification language, evolutions and perspectives....Pages 1-18
The parallel complexity of tree embedding problems (extended abstract)....Pages 19-32
A theory of strict P -completeness....Pages 33-44
Fast and optimal simulations between CRCW PRAMs....Pages 45-56
Suitability of the propositional temporal logic to express properties of real-time systems....Pages 57-70
Axiomatizations of backtracking....Pages 71-82
Joining k - and l -recognizable sets of natural numbers....Pages 83-94
On the performance of networks with multiple busses....Pages 95-108
Efficient algorithms for solving systems of linear equations and path problems....Pages 109-119
Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition....Pages 121-132
A simplified technique for hidden-line elimination in terrains....Pages 133-146
A competitive analysis of nearest neighbor based algorithms for searching unknown scenes....Pages 147-157
Equality and disequality constraints on direct subterms in tree automata....Pages 159-171
Deterministic regular languages....Pages 173-184
The extended low hierarchy is an infinite hierarchy....Pages 185-198
Locally definable acceptance types for polynomial time machines....Pages 199-207
The theory of the polynomial many-one degrees of recursive sets is undecidable....Pages 209-218
A plane-sweep algorithm for finding a closest pair among convex planar objects....Pages 219-232
Linear approximation of simple objects....Pages 233-244
Language learning without overgeneralization....Pages 245-256
The log-star revolution....Pages 257-278
Separating counting communication complexity classes....Pages 279-292
A nonlinear lower bound on the practical combinational complexity....Pages 293-302
On complexity classes and algorithmically random languages....Pages 303-317
New time hierarchy results for deterministic TMS....Pages 319-328
Unconditional Byzantine agreement for any number of faulty processors....Pages 329-336
Broadcasting in butterfly and debruijn networks....Pages 337-350
Interval approximations of message causality in distributed executions....Pages 351-362
On the approximability of the maximum common subgraph problem....Pages 363-374
The complexity of colouring circle graphs....Pages 375-388
Graph isomorphism is low for PP....Pages 389-400
A simple linear time algorithm for triangulating three-colored graphs....Pages 401-411
On locally optimal alignments in genetic sequences....Pages 413-423
Secure commitment against a powerful adversary....Pages 425-436
Communication efficient Zero-knowledge Proofs of knowledge....Pages 437-448
Four results on randomized incremental constructions....Pages 449-460
Enclosing many boxes by an optimal pair of boxes....Pages 461-474
Performance driven k -layer wiring....Pages 475-486
Synthesis for testability: Binary Decision Diagrams....Pages 487-500
Compression and entropy....Pages 501-512
Iterative devices generating infinite words....Pages 513-528
On the factorization conjecture....Pages 529-543
Conditional semi-Thue systems for presenting monoids....Pages 545-556
A combinatorial bound for linear programming and related problems....Pages 557-565
In-place linear probing sort....Pages 567-579
Speeding up two string-matching algorithms....Pages 581-587
The ANIGRAF system....Pages 589-600
A programming language for symbolic computation of regular languages, automata and semigroups....Pages 601-604
ΜSPEED: a system for the specification and verification of microprocessors....Pages 605-606
A discrete event simulator of communication algorithms in interconnection networks....Pages 607-608
ALPHA DU CENTAUR: An environment for the design of systolic arrays....Pages 609-610
Verification of communicating processes by means of automata reduction and abstraction....Pages 611-612
Distributed system simulator (DSS)....Pages 613-614
An interactive proof tool for process algebras....Pages 615-616
SPECI90 A term rewriting and narrowing system....Pages 617-618
....Pages 619-620