Lecture Notes in Computer Science

Structuring and modularizing algebraic specifications: the PLUSS specification language, evolutions and perspectives.- The parallel complexity of tree embedding problems (extended abstract).- A theory of strict P-completeness.- Fast and optimal simulations between CRCW PRAMs.- Suitability of the propositional temporal logic to express properties of real-time systems.- Axiomatizations of backtracking.- Joining k- and l-recognizable sets of natural numbers.- On the performance of networks with multiple busses.- Efficient algorithms for solving systems of linear equations and path problems.- Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition.- A simplified technique for hidden-line elimination in terrains.- A competitive analysis of nearest neighbor based algorithms for searching unknown scenes.- Equality and disequality constraints on direct subterms in tree automata.- Deterministic regular languages.- The extended low hierarchy is an infinite hierarchy.- Locally definable acceptance types for polynomial time machines.- The theory of the polynomial many-one degrees of recursive sets is undecidable.- A plane-sweep algorithm for finding a closest pair among convex planar objects.- Linear approximation of simple objects.- Language learning without overgeneralization.- The log-star revolution.- Separating counting communication complexity classes.- A nonlinear lower bound on the practical combinational complexity.- Characterizations of some complexity classes between ? 2 p and ? 2 p .- On complexity classes and algorithmically random languages.- New time hierarchy results for deterministic TMS.- Unconditional Byzantine agreement for any number of faulty processors.- Broadcasting in butterfly and debruijn networks.- Interval approximations of message causality in distributed executions.- On the approximability of the maximum common subgraph problem.- The complexity of colouring circle graphs.- Graph isomorphism is low for PP.- A simple linear time algorithm for triangulating three-colored graphs.- On locally optimal alignments in genetic sequences.- Secure commitment against a powerful adversary.- Communication efficient Zero-knowledge Proofs of knowledge.- Four results on randomized incremental constructions.- Enclosing many boxes by an optimal pair of boxes.- Performance driven k-layer wiring.- Synthesis for testability: Binary Decision Diagrams.- Compression and entropy.- Iterative devices generating infinite words.- On the factorization conjecture.- Conditional semi-Thue systems for presenting monoids.- A combinatorial bound for linear programming and related problems.- In-place linear probing sort.- Speeding up two string-matching algorithms.- The ANIGRAF system.- A programming language for symbolic computation of regular languages, automata and semigroups.- ?SPEED: a system for the specification and verification of microprocessors.- A discrete event simulator of communication algorithms in interconnection networks.- ALPHA DU CENTAUR: An environment for the design of systolic arrays.- Verification of communicating processes by means of automata reduction and abstraction.- Distributed system simulator (DSS).- An interactive proof tool for process algebras.- SPECI90 A term rewriting and narrowing system.