LEADER 06922nam 22007455 450 001 9910483847403321 005 20251226203523.0 024 7 $a10.1007/11549345 035 $a(CKB)1000000000213218 035 $a(SSID)ssj0000318806 035 $a(PQKBManifestationID)11255714 035 $a(PQKBTitleCode)TC0000318806 035 $a(PQKBWorkID)10311059 035 $a(PQKB)10724169 035 $a(DE-He213)978-3-540-31867-5 035 $a(MiAaPQ)EBC3067832 035 $a(PPN)123097169 035 $a(EXLCZ)991000000000213218 100 $a20100722d2005 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aMathematical Foundations of Computer Science 2005 $e30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings /$fedited by Joanna Jedrzejowicz, Andrzej Szepietowski 205 $a1st ed. 2005. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2005. 215 $a1 online resource (XVI, 814 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v3618 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-31867-4 311 08$a3-540-28702-7 320 $aIncludes bibliographical references and index. 327 $aInvited Lectures -- Page Migration in Dynamic Networks -- Knot Theory, Jones Polynomial and Quantum Computing -- Interactive Algorithms 2005 -- Some Computational Issues in Membrane Computing -- The Generalization of Dirac?s Theorem for Hypergraphs -- On the Communication Complexity of Co-linearity Problems -- An Invitation to Play -- Papers -- The Complexity of Satisfiability Problems: Refining Schaefer?s Theorem -- On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions -- Pure Nash Equilibria in Games with a Large Number of Actions -- On the Complexity of Depth-2 Circuits with Threshold Gates -- Isomorphic Implication -- Abstract Numeration Systems and Tilings -- Adversarial Queueing Model for Continuous Network Dynamics -- Coloring Sparse Random k-Colorable Graphs in Polynomial Expected Time -- Regular Sets of Higher-Order Pushdown Stacks -- Linearly Bounded Infinite Graphs -- Basic Properties for Sand Automata -- A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs -- Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix -- New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling -- Approximating Polygonal Objects by Deformable Smooth Surfaces -- Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications -- Asynchronous Deterministic Rendezvous in Graphs -- Zeta-Dimension -- Online Interval Coloring with Packing Constraints -- Separating the Notions of Self- and Autoreducibility -- Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata -- Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs -- Matrix and Graph Orders Derived from Locally ConstrainedGraph Homomorphisms -- Packing Weighted Rectangles into a Square -- Nondeterministic Graph Searching: From Pathwidth to Treewidth -- Goals in the Propositional Horn??? Language Are Monotone Boolean Circuits -- Autoreducibility, Mitoticity, and Immunity -- Canonical Disjoint NP-Pairs of Propositional Proof Systems -- Complexity of DNF and Isomorphism of Monotone Formulas -- The Expressive Power of Two-Variable Least Fixed-Point Logics -- Languages Representable by Vertex-Labeled Graphs -- On the Complexity of Mixed Discriminants and Related Problems -- Two Logical Hierarchies of Optimization Problems over the Real Numbers -- Algebras as Knowledge Structures -- Combining Self-reducibility and Partial Information Algorithms -- Complexity Bounds for Regular Games -- Basic Mereology with Equivalence Relations -- Online and Dynamic Recognition of Squarefree Strings -- Shrinking Restarting Automata -- Removing Bidirectionality from Nondeterministic Finite Automata -- Generating All Minimal Integral Solutions to Monotone ?,?-Systems of Linear, Transversal and Polymatroid Inequalities -- On the Parameterized Complexity of Exact Satisfiability Problems -- Approximating Reversal Distance for Strings with Bounded Number of Duplicates -- Random Databases and Threshold for Monotone Non-recursive Datalog -- An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems -- Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing -- Tight Approximability Results for the Maximum Solution Equation Problem over Z p -- The Complexity of Model Checking Higher Order Fixpoint Logic -- An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules -- Inverse Monoids: Decidability and Complexity of Algebraic Questions -- Dimension IsCompression -- Concurrent Automata vs. Asynchronous Systems -- Completeness and Degeneracy in Information Dynamics of Cellular Automata -- Strict Language Inequalities and Their Decision Problems -- Event Structures for the Collective Tokens Philosophy of Inhibitor Nets -- An Exact 2.9416 n Algorithm for the Three Domatic Number Problem -- D-Width: A More Natural Measure for Directed Tree Width -- On Beta-Shifts Having Arithmetical Languages -- A BDD-Representation for the Logic of Equality and Uninterpreted Functions -- On Small Hard Leaf Languages -- Explicit Inapproximability Bounds for the Shortest Superstring Problem -- Stratified Boolean Grammars. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v3618 606 $aComputer science 606 $aAlgorithms 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aArtificial intelligence$xData processing 606 $aTheory of Computation 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aData Science 606 $aComputer Science Logic and Foundations of Programming 615 0$aComputer science. 615 0$aAlgorithms. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aArtificial intelligence$xData processing. 615 14$aTheory of Computation. 615 24$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aData Science. 615 24$aComputer Science Logic and Foundations of Programming. 676 $a004.0151 701 $aJedrzejowicz$b Joanna$01752938 701 $aSzepietowski$b Andrzej$0714670 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910483847403321 996 $aMathematical foundations of computer science 2005$94188447 997 $aUNINA