STACS 94

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

AvPatrice Enjalbert,Ernst W. Mayr

Häftad, Engelska, 1994

Del i serien Lecture Notes in Computer Science

552 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Beskrivning

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.

Produktinformation

Utgivningsdatum:1994-02-09
Mått:155 x 235 x 43 mm
Vikt:1 194 g
Format:Häftad
Språk:Engelska
Serie:Lecture Notes in Computer Science
Antal sidor:786
Upplaga:1994
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783540577850

Utforska kategorier

Systemvetenskap och AI inom Data och IT

Innehållsförteckning

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.