000 05825nam a22005775i 4500
001 978-3-642-03816-7
003 DE-He213
005 20240730185635.0
007 cr nn 008mamaa
008 100301s2009 gw | s |||| 0|eng d
020 _a9783642038167
_9978-3-642-03816-7
024 7 _a10.1007/978-3-642-03816-7
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aMathematical Foundations of Computer Science 2009
_h[electronic resource] :
_b34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009, Proceedings /
_cedited by Rastislav Královic, Damian Niwinski.
250 _a1st ed. 2009.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2009.
300 _aXV, 760 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5734
505 0 _aInvited Papers -- Four Subareas of the Theory of Constraints, and Their Links -- Synchronization of Regular Automata -- Stochastic Process Creation -- Stochastic Games with Finitary Objectives -- Stochastic Data Streams -- Recent Advances in Population Protocols -- How to Sort a Train -- Contributed Papers -- Arithmetic Circuits, Monomial Algebras and Finite Automata -- An Improved Approximation Bound for Spanning Star Forest and Color Saving -- Energy-Efficient Communication in Multi-interface Wireless Networks -- Private Capacities in Mechanism Design -- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules -- Sampling Edge Covers in 3-Regular Graphs -- Balanced Paths in Colored Graphs -- Few Product Gates But Many Zeros -- Branching Programs for Tree Evaluation -- A Dichotomy Theorem for Polynomial Evaluation -- DP-Complete Problems Derived from Extremal NP-Complete Properties -- The Synchronization Problem for Locally Strongly Transitive Automata -- Constructing Brambles -- Self-indexed Text Compression Using Straight-Line Programs -- Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants -- Parameterized Complexity Classes under Logical Reductions -- The Communication Complexity of Non-signaling Distributions -- How to Use Spanning Trees to Navigate in Graphs -- Representing Groups on Graphs -- Admissible Strategies in Infinite Games over Graphs -- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems -- Future-Looking Logics on Data Words and Trees -- A By-Level Analysis of Multiplicative Exponential Linear Logic -- Hyper-minimisation Made Efficient -- Regular Expressions with Counting: Weak versus Strong Determinism -- Choosability of P 5-Free Graphs -- Time-Bounded Kolmogorov Complexity and Solovay Functions -- The Longest Path Problem Is Polynomial on Interval Graphs -- Synthesis for Structure Rewriting Systems -- On the Hybrid Extension of CTL and CTL?+? -- Bounds on Non-surjective Cellular Automata -- FO Model Checking on Nested Pushdown Trees -- The Prismoid of Resources -- A Dynamic Algorithm for Reachability Games Played on Trees -- An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable -- Graph Decomposition for Improving Memoryless Periodic Exploration -- On FO 2 Quantifier Alternation over Words -- On the Recognizability of Self-generating Sets -- The Isomorphism Problem for k-Trees Is Complete for Logspace -- Snake-Deterministic Tiling Systems -- Query Automata for Nested Words -- A General Class of Models of -- The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I -- Colouring Non-sparse Random Intersection Graphs -- On the Structure of Optimal Greedy Computation (for Job Scheduling) -- A Probabilistic PTAS for Shortest Common Superstring -- The Cost of Stability in Network Flow Games -- (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata -- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm -- From Parity and Payoff Games to Linear Programming -- Partial Randomness and Dimension of Recursively Enumerable Reals -- Partial Solution and Entropy -- On Pebble Automata for Data Languages with Decidable Emptiness Problem -- Size and Energy of Threshold Circuits Computing Mod Functions -- Points on Computable Curves of Computable Lengths -- The Expressive Power of Binary Submodular Functions.
650 0 _aComputer science.
_99832
650 0 _aAlgorithms.
_93390
650 0 _aMachine theory.
_9140105
650 0 _aComputer science
_xMathematics.
_93866
650 1 4 _aTheory of Computation.
_9140106
650 2 4 _aAlgorithms.
_93390
650 2 4 _aComputer Science Logic and Foundations of Programming.
_942203
650 2 4 _aFormal Languages and Automata Theory.
_9140107
650 2 4 _aMathematics of Computing.
_931875
700 1 _aKrálovic, Rastislav.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9140108
700 1 _aNiwinski, Damian.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9140109
710 2 _aSpringerLink (Online service)
_9140110
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783642038150
776 0 8 _iPrinted edition:
_z9783642038174
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5734
_9140111
856 4 0 _uhttps://doi.org/10.1007/978-3-642-03816-7
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c92929
_d92929