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

The nature and meaning of perturbations in geometric computing....Pages 1-17
One binary horn clause is enough....Pages 19-32
Transforming constraint logic programs....Pages 33-46
A hierarchy of temporal logics with past....Pages 47-58
The complexity of resource-bounded first-order classical logic....Pages 59-70
Two proof procedures for a cardinality based language in propositional calculus....Pages 71-82
The alternation hierarchy for machines with sublogarithmic space is infinite....Pages 83-96
Quasilinear time complexity theory....Pages 97-108
Space-efficient deterministic simulation of probabilistic automata....Pages 109-122
Reachability and the power of local ordering....Pages 123-135
Are parallel machines always faster than sequential machines?....Pages 137-148
Ground reducibility and automata with disequality constraints....Pages 149-162
Perpetuality and strong normalization in orthogonal term rewriting systems....Pages 163-174
About changing the ordering during Knuth-Bendix completion....Pages 175-186
Combination of matching algorithms....Pages 187-198
Periodic constant depth sorting networks....Pages 199-212
Optimal pattern matching on meshes....Pages 213-224
Faster sorting and routing on grids with diagonals....Pages 225-236
Deterministic 1 - k routing on meshes with applications to worm-hole routing....Pages 237-248
A unifying type-theoretic framework for objects....Pages 249-262
Operational specifications with built-ins....Pages 263-274
Reactive variables for system specification and design....Pages 275-286
A new parallel vector model, with exact characterization of NC k ....Pages 287-300
On adaptive dlogtime and polylogtime reductions....Pages 301-312
NC k (NP)=AC k−1 (NP)....Pages 313-324
Hypertransition systems....Pages 325-338
On the star operation and the finite power property in free partially commutative monoids....Pages 339-352
Coding with traces....Pages 353-364
Monadic second-order logic over pictures and recognizability by tiling systems....Pages 365-375
Q-grammars: Results, implementation....Pages 377-388
A topology for complete semirings....Pages 389-400
The global power of additional queries to random oracles....Pages 401-414
Cook versus Karp-Levin: Separating completeness notions if NP is not small....Pages 415-426
On sets bounded truth-table reducible to P-selective sets....Pages 427-438
Two refinements of the polynomial hierarchy....Pages 439-448
On different reducibility notions for function classes....Pages 449-460
Optimal parallelization of Las Vegas algorithms....Pages 461-474
Efficient parallel algorithms for geometric k -clustering problems....Pages 475-486
A simple optimal parallel algorithm for reporting paths in a tree....Pages 487-495
Parallel detection of all palindromes in a string....Pages 497-506
On the structure of parameterized problems in NP....Pages 507-520
On the approximability of finding maximum feasible subsystems of linear systems....Pages 521-532
On the acceptance power of regular languages....Pages 533-541
Complexity classes with finite acceptance types....Pages 543-553
The complete axiomatization of Cs-congruence....Pages 555-568
Transition system specifications in stalk format with bisimulation as a congruence....Pages 569-580
Decidability questions for bisimilarity of Petri nets and some related problems....Pages 581-592
The variable membership problem: Succinctness versus complexity....Pages 593-606
Economy of description for single-valued transducers....Pages 607-618
Automaticity: Properties of a measure of descriptional complexity....Pages 619-630
Towards a theory of recursive structures....Pages 631-645
Finding minimal generalizations for unions of pattern languages and its application to inductive inference from positive data....Pages 647-660
Nondeterminism in patterns....Pages 661-668
Upper bounds for the expected length of a longest common subsequence of two binary sequences....Pages 669-678
The ambiguity of primitive words....Pages 679-690
On codes having no finite completion....Pages 691-698
A new approach to information theory....Pages 699-708
On Voronoi diagrams in the L p -metric in higher dimensions....Pages 709-722
Total protection of analytic invariant information in cross tabulated tables....Pages 723-734
Dominating cliques in graphs with hypertree structure....Pages 735-746
On vertex ranking for permutation and other graphs....Pages 747-758
Finding all minimal separators of a graph....Pages 759-768
On the complexity of the maximum cut problem....Pages 769-780