LEADER 06899nam 22006975 450 001 996465401903316 005 20230406035731.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$b[electronic resource] $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 $a3-540-31867-4 311 $a3-540-28702-7 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 Constrained Graph 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 Is Compression -- 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?Mathematics 606 $aDiscrete mathematics 606 $aArtificial intelligence?Data 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?Mathematics. 615 0$aDiscrete mathematics. 615 0$aArtificial intelligence?Data 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 702 $aJedrzejowicz$b Joanna$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aSzepietowski$b Andrzej$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996465401903316 996 $aMathematical Foundations of Computer Science 2005$9774253 997 $aUNISA