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

Raimund Seidel (auth.), Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner (eds.)3540577858, 9783540577850

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.

---

Table of contents :
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