LEADER 07066nam 22007695 450 001 9910483269703321 005 20230405232745.0 010 $a3-540-74456-8 024 7 $a10.1007/978-3-540-74456-6 035 $a(CKB)1000000000490780 035 $a(SSID)ssj0000318808 035 $a(PQKBManifestationID)11240019 035 $a(PQKBTitleCode)TC0000318808 035 $a(PQKBWorkID)10335941 035 $a(PQKB)10943664 035 $a(DE-He213)978-3-540-74456-6 035 $a(MiAaPQ)EBC3063300 035 $a(MiAaPQ)EBC6698703 035 $a(Au-PeEL)EBL6698703 035 $a(PPN)123164508 035 $a(EXLCZ)991000000000490780 100 $a20100301d2007 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aMathematical Foundations of Computer Science 2007 $e32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings /$fedited by Ludek Kucera, Antonín Kucera 205 $a1st ed. 2007. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2007. 215 $a1 online resource (XVIII, 766 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4708 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-74455-X 320 $aIncludes bibliographical references and index. 327 $aInvited Papers -- How To Be Fickle -- Finite Model Theory on Tame Classes of Structures -- Minimum Cycle Bases in Graphs Algorithms and Applications -- Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes -- Evolvability -- Random Graphs -- Expander Properties and the Cover Time of Random Intersection Graphs -- Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs -- Rewriting -- Transition Graphs of Rewriting Systems over Unranked Trees -- Rewriting Conjunctive Queries Determined by Views -- Approximation Algorithms -- Approximation Algorithms for the Maximum Internal Spanning Tree Problem -- New Approximability Results for 2-Dimensional Packing Problems -- On Approximation of Bookmark Assignments -- Automata and Circuits -- Height-Deterministic Pushdown Automata -- Minimizing Variants of Visibly Pushdown Automata -- Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids -- Complexity I -- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete -- NP by Means of Lifts and Shadows -- The Complexity of Solitaire -- Streams and Compression -- Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems -- Space-Conscious Compression -- Graphs I -- Small Alliances in Graphs -- The Maximum Solution Problem on Graphs -- Iteration and Recursion -- What Are Iteration Theories? -- Properties Complementary to Program Self-reference -- Algorithms I -- Dobrushin Conditions for Systematic Scan with Block Dynamics -- On the Complexity of Computing Treelength -- On Time Lookahead Algorithms for the Online Data Acknowledgement Problem -- Automata -- Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-convex Neighborhoods -- Towards a Rice Theorem on Traces of Cellular Automata -- Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority -- Complexity II -- Public Key Identification Based on the Equivalence of Quadratic Forms -- Reachability Problems in Quaternion Matrix and Rotation Semigroups -- VPSPACE and a Transfer Theorem over the Complex Field -- Protocols -- Efficient Provably-Secure Hierarchical Key Assignment Schemes -- Nearly Private Information Retrieval -- Graphs II -- Packing and Squeezing Subgraphs into Planar Graphs -- Dynamic Matchings in Convex Bipartite Graphs -- Networks -- Communication in Networks with Random Dependent Faults -- Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults -- Algorithms II -- A Linear Time Algorithm for the k Maximal Sums Problem -- A Lower Bound of 1?+?? for Truthful Scheduling Mechanisms -- Analysis of Maximal Repetitions in Strings -- Languages -- Series-Parallel Languages on Scattered and Countable Posets -- Traces of Term-Automatic Graphs -- State Complexity of Basic Operations on Suffix-Free Regular Languages -- Graphs III -- Exact Algorithms for L(2,1)-Labeling of Graphs -- On (k,?)-Leaf Powers -- Quantum Computing -- An Improved Claw Finding Algorithm Using Quantum Walk -- Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument -- Isomorphism -- On the Complexity of Game Isomorphism -- Hardness Results for Tournament Isomorphism and Automorphism -- Relating Complete and Partial Solution for Problems Similar to Graph Automorphism -- Equilibria -- Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach -- Selfish Load Balancing Under Partial Knowledge -- Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria -- Games -- Congestion Games with Player-Specific Constants -- Finding Patterns in Given Intervals -- The Power of Two Prices: Beyond Cross-Monotonicity -- Algebra and Strings -- Semisimple Algebras of Almost Minimal Rank over the Reals -- Structural Analysis of Gapped Motifs of a String -- Algorithms III -- Online and Offline Access to Short Lists -- Optimal Randomized Comparison Based Algorithms for Collision -- Randomized and Approximation Algorithms for Blue-Red Matching -- Words and Graphs -- Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation -- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances -- Shuffle Expressions and Words with Nested Data. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4708 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 $a518.1 702 $aKuc?era$b Lude?k 702 $aKuc?era$b Antoni?n$f1971- 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910483269703321 996 $aMathematical Foundations of Computer Science 2007$9772560 997 $aUNINA