STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings (Lecture Notes in Computer Science, 1373)

This Book Constitutes The Strictly Refereed Proceedings Of The 15th Annual Symposium On Theoretical Aspects Of Computer Science, Stacs 98, Held In Paris, France, In February 1998. The Volume Presents Three Invited Surveys Together With 52 Revised Full Papers Selected From A Total Of 155 Submissions. The Papers Are Organized In Topical Sections On Algorithms And Data Structures, Logic, Complexity, And Automata And Formal Languages. Random Graphs, Random Walks, Differential Equations And The Probabilistic Analysis Of Algorithms -- Distributed Online Frequency Assignment In Cellular Networks -- Floats, Integers, And Single Source Shortest Paths -- A Synthesis On Partition Refinement: A Useful Routine For Strings, Graphs, Boolean Matrices And Automata -- Simplifying The Modal Mu-calculus Alternation Hierarchy -- On Disguised Double Horn Functions And Extensions -- The Complexity Of Propositional Linear Temporal Logics In Simple Cases -- Searching Constant Width Mazes Captures The Ac 0 Hierarchy -- Nearly Optimal Language Compression Using Extractors -- Random Sparse Bit Strings At The Threshold Of Adjacency -- Lower Bounds For Randomized Read-k-times Branching Programs -- Inducing An Order On Cellular Automata By A Grouping Operation -- Attractors Of D-dimensional Linear Cellular Automata -- Optimal Simulations Between Unary Automata -- Shuffle Of ?-words: Algebraic Aspects --^ A Generalization Of Resource-bounded Measure, With An Application (extended Abstract) -- The Complexity Of Modular Graph Automorphism -- Unary Quantifiers, Transitive Closure, And Relations Of Large Degree -- On The Structure Of Valiant's Complexity Classes -- On The Existence Of Polynomial Time Approximation Schemes For Obdd Minimization -- Complexity Of Problems On Graphs Represented As Obdds -- Equivalence Test And Ordering Transformation For Parity-obdds Of Different Variable Ordering -- Size And Structure Of Random Ordered Binary Decision Diagrams -- Provable Security For Block Ciphers By Decorrelation -- On The Approximation Of Finding A(nother) Hamiltonian Cycle In Cubic Hamiltonian Graphs -- The Mutual Exclusion Scheduling Problem For Permutation And Comparability Graphs -- Massaging A Linear Programming Solution To Give A 2-approximation For A Generalization Of The Vertex Cover Problem -- Partially Persistent Search Trees With Transcript Operations --^ Relating Hierarchies Of Word And Tree Automata -- Languages Defined With Modular Counting Quantifiers -- Hierarchies Of Principal Twist-closed Trios -- Radix Representations Of Algebraic Number Fields And Finite Automata -- Sorting And Searching On The Word Ram -- Communication-efficient Deterministic Parallel Algorithms For Planar Point Location And 2d Voronoi Diagram -- On Batcher's Merge Sorts As Parallel Sorting Algorithms -- Minimum Spanning Trees For Minor-closed Graph Classes In Parallel -- Optimal Broadcasting In Almost Trees And Partial K-trees -- Local Normal Forms For First-order Logic With Applications To Games And Automata -- Axiomatizing The Equational Theory Of Regular Tree Languages -- A Logical Characterization Of Systolic Languages -- Optimal Proof Systems For Propositional Logic And Complete Sets -- The (parallel) Approximability Of Non-boolean Satisfiability Problems And Restricted Integer Programming -- Interactive Protocols On The Reals --^ Result-indistinguishable Zero-knowledge Proofs: Increased Power And Constant-round Protocols -- Bounded Size Dictionary Compression: Sck-completeness And Nc Algorithms -- Expressive Completeness Of Ltrl On Finite Traces: An Algebraic Proof -- On Uniform Dol Words -- Series-parallel Posets: Algebra, Automata And Languages -- On The Expected Number Of Nodes At Level K In 0-balanced Trees -- Cell Flipping In Permutation Diagrams -- Construction Of Non-intersecting Colored Flows Through A Planar Cellular Figure -- Recursively Enumerable Reals And Chaitin ? Numbers -- Uniformly Defining Complexity Classes Of Functions -- Recognizability Equals Monadic Second-order Definability For Sets Of Graphs Of Bounded Tree-width. Michel Morvan, Christoph Meinel, Daniel Krob (eds). Includes Bibliographical References And Index. Random graphs, random walks, differential equations and the probabilistic analysis of algorithms....Pages 1-2 Distributed online frequency assignment in cellular networks....Pages 3-13 Floats, integers, and single source shortest paths....Pages 14-24 A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata....Pages 25-38 Simplifying the modal mu-calculus alternation hierarchy....Pages 39-49 On disguised double horn functions and extensions....Pages 50-60 The complexity of propositional linear temporal logics in simple cases....Pages 61-72 Searching constant width mazes captures the A C 0 hierarchy....Pages 73-83 Nearly optimal language compression using extractors....Pages 84-93 Random sparse bit strings at the threshold of adjacency....Pages 94-104 Lower bounds for randomized read- k -times branching programs....Pages 105-115 Inducing an order on cellular automata by a grouping operation....Pages 116-127 Attractors of D -dimensional Linear Cellular Automata....Pages 128-138 Optimal simulations between unary automata....Pages 139-149 Shuffle of ω -words: Algebraic aspects....Pages 150-160 A generalization of resource-bounded measure, with an application (Extended abstract)....Pages 161-171 The complexity of modular graph automorphism....Pages 172-182 Unary quantifiers, transitive closure, and relations of large degree....Pages 183-193 On the structure of valiant's complexity classes....Pages 194-204 On the existence of polynomial time approximation schemes for OBDD minimization....Pages 205-215 Complexity of problems on graphs represented as OBDDs....Pages 216-226 Equivalence test and ordering transformation for parity-OBDDs of different variable ordering....Pages 227-237 Size and structure of random ordered binary decision diagrams....Pages 238-248 Provable security for block ciphers by decorrelation....Pages 249-275 On the approximation of finding A(nother) Hamiltonian cycle in cubic Hamiltonian graphs....Pages 276-286 The mutual exclusion scheduling problem for permutation and comparability graphs....Pages 287-297 Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem....Pages 298-308 Partially persistent search trees with transcript operations....Pages 309-319 Relating hierarchies of word and tree automata....Pages 320-331 Languages defined with modular counting quantifiers....Pages 332-343 Hierarchies of principal twist-closed trios....Pages 344-355 Radix representations of algebraic number fields and finite automata....Pages 356-365 Sorting and searching on the word RAM....Pages 366-398 Communication-efficient deterministic parallel algorithms for planar point location and 2d Voronoi Diagram....Pages 399-409 On Batcher's merge sorts as parallel sorting algorithms....Pages 410-420 Minimum spanning trees for minor-closed graph classes in parallel....Pages 421-431 Optimal broadcasting in almost trees and partial k -trees....Pages 432-443 Local normal forms for first-order logic with applications to games and automata....Pages 444-454 Axiomatizing the equational theory of regular tree languages....Pages 455-465 A Logical Characterization of Systolic Languages....Pages 466-476 Optimal proof systems for propositional logic and complete sets....Pages 477-487 The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming....Pages 488-498 Interactive protocols on the reals....Pages 499-510 Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols....Pages 511-521 Bounded size dictionary compression: SC k -completeness and NC algorithms....Pages 522-532 Expressive completeness of LTrL on finite traces: An algebraic proof....Pages 533-543 On uniform DOL words....Pages 544-554 Series-parallel posets: Algebra, automata and languages....Pages 555-565 On the expected number of nodes at level k in 0-balanced trees....Pages 566-576 Cell flipping in permutation diagrams....Pages 577-586 Construction of non-intersecting colored flows through a planar cellular figure....Pages 587-595 Recursively enumerable reals and chaitin Ω numbers....Pages 596-606 Uniformly defining complexity classes of functions....Pages 607-617 Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width....Pages 618-628