LEADER 06238nam 2200577 a 450 001 9910483628803321 005 20200520144314.0 010 $a3-540-37793-X 024 7 $a10.1007/11821069 035 $a(CKB)1000000000283919 035 $a(SSID)ssj0000318807 035 $a(PQKBManifestationID)11265699 035 $a(PQKBTitleCode)TC0000318807 035 $a(PQKBWorkID)10336496 035 $a(PQKB)10125720 035 $a(DE-He213)978-3-540-37793-1 035 $a(MiAaPQ)EBC3068133 035 $a(PPN)123137659 035 $a(EXLCZ)991000000000283919 100 $a20060712d2006 uy 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aMathematical foundations of computer science 2006 $e31th international symposium, MFCS 2006, Stara Lesna, Slovakia, August 28- September 1, 2006 : proceedings /$fRastislav Kralovic, Pawe Urzyczyn (eds.) 205 $a1st ed. 2006. 210 $aBerlin ;$aNew York $cSpringer$d2006 215 $a1 online resource (XVI, 816 p.) 225 1 $aLecture notes in computer science,$x0302-9743 ;$v4162 225 1 $aLNCS sublibrary. SL 1, Theoretical computer science and general issues 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-37791-3 320 $aIncludes bibliographical references and index. 327 $aInvited Talks -- A Core Calculus for Scala Type Checking -- Tree Exploration with an Oracle -- Distributed Data Structures: A Survey on Informative Labeling Schemes -- From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions -- The Structure of Tractable Constraint Satisfaction Problems -- On the Representation of Kleene Algebras with Tests -- From Three Ideas in TCS to Three Applications in Bioinformatics -- Contributed Papers -- Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles -- Approximate Shortest Path Queries on Weighted Polyhedral Surfaces -- A Unified Construction of the Glushkov, Follow, and Antimirov Automata -- Algebraic Characterizations of Unitary Linear Quantum Cellular Automata -- A Polynomial Time Nilpotence Test for Galois Groups and Related Results -- The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems -- Crochemore Factorization of Sturmian and Other Infinite Words -- Equations on Partial Words -- Concrete Multiplicative Complexity of Symmetric Functions -- On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures -- Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities -- The Kleene Equality for Graphs -- On the Repetition Threshold for Large Alphabets -- Improved Parameterized Upper Bounds for Vertex Cover -- On Comparing Sums of Square Roots of Small Integers -- A Combinatorial Approach to Collapsing Words -- Optimal Linear Arrangement of Interval Graphs -- The Lempel-Ziv Complexity of Fixed Points of Morphisms -- Partially Commutative Inverse Monoids -- Learning Bayesian Networks Does Not Have to Be NP-Hard -- Lower Bounds for the Transition Complexity of NFAs -- Smart Robot Teams Exploring Sparse Trees -- k-Sets of Convex Inclusion Chains of Planar Point Sets -- Toward the Eigenvalue Power Law -- Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves -- Very Sparse Leaf Languages -- On the Correlation Between Parity and Modular Polynomials -- Optimally Fast Data Gathering in Sensor Networks -- Magic Numbers in the State Hierarchy of Finite Automata -- Online Single Machine Batch Scheduling -- Machines that Can Output Empty Words -- Completeness of Global Evaluation Logic -- NOF-Multiparty Information Complexity Bounds for Pointer Jumping -- Dimension Characterizations of Complexity Classes -- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems -- An Expressive Temporal Logic for Real Time -- On Matroid Representability and Minor Problems -- Non-cooperative Tree Creation -- Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners -- Reductions for Monotone Boolean Circuits -- Generalised Integer Programming Based on Logically Defined Relations -- Probabilistic Length-Reducing Automata -- Sorting Long Sequences in a Single Hop Radio Network -- Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture -- Valiant?s Model: From Exponential Sums to Exponential Products -- A Reachability Algorithm for General Petri Nets Based on Transition Invariants -- Approximability of Bounded Occurrence Max Ones -- Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability -- Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes -- Quantum Weakly Nondeterministic Communication Complexity -- Minimal Chordal Sense of Direction and Circulant Graphs -- Querying and Embedding Compressed Texts -- Lempel-Ziv Dimension for Lempel-Ziv Compression -- Characterizing Valiant?s Algebraic Complexity Classes -- The Price of Defense -- The Data Complexity of MDatalog in Basic Modal Logics -- The Complexity of Counting Functions with Easy Decision Version -- On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model -- Constrained Minimum Enclosing Circle with Center on a Query Line Segment -- Hierarchical Unambiguity -- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the ?erny Conjecture -- On Genome Evolution with Innovation. 410 0$aLecture notes in computer science ;$v4162. 410 0$aLNCS sublibrary.$nSL 1,$pTheoretical computer science and general issues. 517 3 $aMFCS 2006 606 $aComputer science$xMathematics$vCongresses 615 0$aComputer science$xMathematics 676 $a004.0151 701 $aKralovic$b Rastislav$01762326 701 $aUrzyczyn$b Pawe$0318886 712 12$aSymposium on Mathematical Foundations of Computer Science (1972- ) 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910483628803321 996 $aMathematical foundations of computer science 2006$94202186 997 $aUNINA