STACS 94 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24–26, 1994 Proceedings

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 partially commutative monoids.- Coding with traces.- Monadic second-order logic over pictures and recognizability by tiling systems.- Q-grammars: Results, implementation.- A topology for complete semirings.- The global power of additional queries to random oracles.- Cook versus Karp-Levin: Separating completeness notions if NP is not small.- Onsets bounded truth-table reducible to P-selective sets.- Two refinements of the polynomial hierarchy.- On different reducibility notions for function classes.- Optimal parallelization of Las Vegas algorithms.- Efficient parallel algorithms for geometric k-clustering problems.- A simple optimal parallel algorithm for reporting paths in a tree.- Parallel detection of all palindromes in a string.- On the structure of parameterized problems in NP.- On the approximability of finding maximum feasible subsystems of linear systems.- On the acceptance power of regular languages.- Complexity classes with finite acceptance types.- The complete axiomatization of Cs-congruence.- Transition system specifications in stalk format with bisimulation as a congruence.- Decidability questions for bisimilarity of Petri nets and some related problems.- The variable membership problem: Succinctness versus complexity.- Economy of description for single-valued transducers.- Automaticity: Properties of a measure of descriptional complexity.- Towards a theory of recursive structures.- Finding minimal generalizations for unions of pattern languages and its application to inductive inference from positive data.- Nondeterminism in patterns.- Upper bounds for the expected length of a longest common subsequence of two binary sequences.- The ambiguity of primitive words.- On codes having no finite completion.- A new approach to information theory.- On Voronoi diagrams in the L p -metric in higher dimensions.- Total protection of analytic invariant information in cross tabulated tables.- Dominating cliques in graphs with hypertree structure.- On vertex ranking for permutation and other graphs.- Finding all minimal separators of a graph.- On the complexity of the maximum cut problem.