06231nam a22006375i 4500001001800000003000900018005001700027007001500044008004100059020003700100024002800137050001700165072001500182072001600197072002300213072002300236082001700259245021300276264006100489300003400550336002600584337002600610338003600636347002400672490005800696505363900754520043904393650002204832650002604854650004004880650001504920650002404935650003504959650002304994650002205017650002705039650002805066650004605094650002305140650002105163650002305184700002905207700003205236700002705268710003405295773002005329776003605349830005805385856004105443912001405484912001405498912001405512942001205526950003805538999001705576978-3-540-69705-3DE-He21320170515111459.0cr nn 008mamaa121227s1998 gw | s |||| 0|eng d a97835406970539978-3-540-69705-37 a10.1007/BFb00285422doi 4aQA75.5-76.95 7aUY2bicssc 7aUYA2bicssc 7aCOM0140002bisacsh 7aCOM0310002bisacsh04a004.015122310aSTACS 98h[electronic resource] :b15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998 Proceedings /cedited by Michel Morvan, Christoph Meinel, Daniel Krob. 1aBerlin, Heidelberg :bSpringer Berlin Heidelberg,c1998. aXVI, 636 p.bonline resource. atextbtxt2rdacontent acomputerbc2rdamedia aonline resourcebcr2rdacarrier atext filebPDF2rda1 aLecture Notes in Computer Science,x0302-9743 ;v13730 aRandom 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. aThis 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. 0aComputer science. 0aComputer programming. 0aData encryption (Computer science). 0aComputers. 0aNumerical analysis. 0aComputer sciencexMathematics. 0aComputer graphics.14aComputer Science.24aTheory of Computation.24aProgramming Techniques.24aDiscrete Mathematics in Computer Science.24aComputer Graphics.24aData Encryption.24aNumeric Computing.1 aMorvan, Michel.eeditor.1 aMeinel, Christoph.eeditor.1 aKrob, Daniel.eeditor.2 aSpringerLink (Online service)0 tSpringer eBooks08iPrinted edition:z9783540642305 0aLecture Notes in Computer Science,x0302-9743 ;v137340uhttp://dx.doi.org/10.1007/BFb0028542 aZDB-2-SCS aZDB-2-LNC aZDB-2-BAE 2ddccEB aComputer Science (Springer-11645) c14584d14584