Lecture Notes in Computer Science

On the semantics of logic programs.- Logic programming with recurrence domains.- Extensional embedding of a strongly stable model of PCF.- Uniform ideals and strictness analysis.- Logical and computational aspects of programming with sets/bags/lists.- Safety for branching time semantics.- Program composition and modular verification.- Model-checking for probabilistic real-time systems.- Computing behavioural relations, logically.- The power of reconfiguration.- General resolution of tseitin formulas is hard.- Program checkers for probability generation.- Running time to recognize nonregular languages by 2-way probabilistic automata.- Statistics on random trees.- The expressive power of implicit specifications.- CCS + time = an interleaving model for real time systems.- On confluent semi-commutations - Decidability and complexity results.- Lazard's factorizations of free partially commutative monoids.- A Kleene theorem for infinite trace languages.- Canonical sets of horn clauses.- A specialized completion procedure for monadic string-rewriting systems presenting groups.- A confluent reduction for the ?-calculus with surjective pairing and terminal object.- Provably recursive programs and program extraction.- Efficient algorithms for path problems with general cost criteria.- Computing shortest paths and distances in planar graphs.- Maintaining biconnected components of dynamic planar graphs.- Efficient maximal cubic graph cuts.- Structural parallel algorithmics.- Improving known solutions is hard.- Collapsing degrees via strong computation.- Fast parallel generation of random permutations.- A parallel algorithm for two processors precedence constraint scheduling.- An efficient NC algorithm for finding Hamiltonian cycles in dense directed graphs.- On logics, tilings, and automata.- Satisfiability of systems of ordinal notations with the subterm property is decidable.- Complete axiomatizations of some quotient term algebras.- The meaning of negative premises in transition system specifications.- Deciding history preserving bisimilarity.- Adding action refinement to a finite process algebra.- Improved parallel computations with matrices and polynomials.- Finding minimal forbidden minors using a finite congruence.- Better algorithms for the pathwidth and treewidth of graphs.- Two P-complete problems in the theory of the reals.- L morphisms: Bounded delay and regularity of ambiguity.- Degree and decomposability of variable-length codes.- An EILENBERG theorem for ?-languages.- Balancing order and chaos in image generation.- Average case complexity.- Minimal NFA problems are hard.- Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language.- Computing shortest transversals.- Ray shooting in polygons using geodesic triangulations.- The expected extremes in a delaunay triangulation.- Computational geometry for the gourmet old fare and new dishes.- On the power of multiple reads in a chip.- On linear decision trees computing Boolean functions.- An almost linear-time algorithm for the dense subset-sum problem.- On-line algorithms for weighted bipartite matching and stable marriages.- String matching with preprocessing of text and pattern.- Ordering problems approximated: single-processor scheduling and interval graph completion.