Stacs 94: 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24-26, 1994 Proceedings

ISBN-13: 9783540577850 / Angielski / Miękka / 1994 / 786 str.

Patrice Enjalbert; Ernst W. Mayr; Klaus W. Wagner

Opis

This volume of conference proceedings contains 60 papers presenting a wide range of issues in theoretical computer science. Emphasis has been placed on parallel algorithms and complexity theory.

Spis treści

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.- On sets 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.