STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 2426, 1994 Proceedings [Paperback]

This volume constitutes the proceedings of the 11th annual Symposium on Theoretical Aspects of Computer Science (STACS '94), held in Caen, France, February 24-26, 1994. Besides three prominent invited papers, the proceedings contains 60 accepted contributions chosen by the international program committee during a highly competitive reviewing process from a total of 234 submissions for 38 countries. The volume competently represents most areas of theoretical computer science with a certain emphasis on (parallel) algorithms and complexity.The nature and meaning of perturbations in geometric computing.- One binary horn clause is enough.- Transforming constraint logic programs.- A hierarchy of temporal logics with past.- The complexity of resource-bounded first-order classical logic.- Two proof procedures for a cardinality based language in propositional calculus.- The alternation hierarchy for machines with sublogarithmic space is infinite.- Quasilinear time complexity theory.- Space-efficient deterministic simulation of probabilistic automata.- Reachability and the power of local ordering.- Are parallel machines always faster than sequential machines?.- Ground reducibility and automata with disequality constraints.- Perpetuality and strong normalization in orthogonal term rewriting systems.- About changing the ordering during Knuth-Bendix completion.- Combination of matching algorithms.- Periodic constant depth sorting networks.- Optimal pattern matching on meshes.- Faster sorting and routing on grids with diagonals.- Deterministic 1 -k routing on meshes with applications to worm-hole routing.- A unifying type-theoretic framework for objects.- Operational specifications with built-ins.- Reactive variables for system specification and design.- A new parallel vector model, with exact characterization of NCk.- On adaptive dlogtime and polylogtime reductions.- NCk(NP)=AC k?1(NP).- Hypertransition systems.- On the star operation and the finite power property in free partialC