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

Marie-Claude Gaudel (auth.), Alain Finkel, Matthias Jantzen (eds.)3540552103, 9783540552109

This volume gives the proceedings of the ninth Symposium on Theoretical Aspects of Computer Science (STACS). This annual symposium is held alternately in France and Germany and is organized jointly by the Special Interest Group for Fundamental Computer Science of the Association Francaise des Sciences et Technologies de l’Information et des Syst mes (AFCET) and the Special Interest Group for Theoretical Computer Science of the Gesellschaft f}r Informatik (GI). The volume includes three invited lectures and sections on parallel algorithms, logic and semantics, computational geometry, automata and languages, structural complexity, computational geometry and learning theory, complexity and communication, distributed systems, complexity, algorithms, cryptography, VLSI, words and rewriting, and systems.

---

Table of contents :
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