На этой странице можно скачать этот файл совершенно бесплатно и без регистрации и без отправки смс, а также без различного рода ограничений.
Скачивайте и учитесь, надеемся, наш сайт помог вам "погрызть гранит науки"
Kralovi?c R., Niwi?nski D. (Eds.) Mathematical Foundations of Computer Science 2009
Springer, 2009. 760 р. ISSN 0302-9743 (на английском языке) 34 th International Symposium, MFCS 2009 Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009 Proceedings Table of Contents Invited Papers Four Subareas ofthe TheoryofConstraints, and Their Links Albert Atserias Synchronization of Regular Automata Didier Caucal Stochastic Process Creation Javier Esparza StochasticGames with Finitary Objectives Krishnendu Chatterjee, Thomas A. Henzinger, and Florian Horn Stochastic Data Streams S. Muthukrishnan Recent Advances in Population Protocols Ioannis Chatzigiannakis, Othon Michail, and Paul G. Spirakis How toSort a Train Peter Widmayer Contributed Papers ArithmeticCircuits,MonomialAlgebras and Finite Automata Vikraman Arvind and Pushkar S. Joglekar An Improved Approximation Boundfor Spanning Star Forest and Color Saving Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, and Maria Kyropoulou Energy-E?cientCommunicationinMulti-interface Wireless Networks Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, and Evi Papaioannou Private Capacities in Mechanism Design Vincenzo Auletta, Paolo Penna, and Giuseppe Persiano Towards a Dichotomyof Finding Possible Winners in Elections Based on ScoringRules Nadja Betzler and Britta Dorn SamplingEdgeCovers in 3-Regular Graphs Ivona Bez? akov? a and William A. Rummler Balanced Paths in Colored Graphs Alessandro Bianco, Marco Faella, Fabio Mogavero, and Aniel lo Murano FewProduct Gates But Many Zeros Bernd Borchert, Pierre McKenzie, and Klaus Reinhardt Branching Programs for Tree Evaluation Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam, and Dustin Wehr ADichotomyTheorem for Polynomial Evaluation Ir? en? ee Briquel and Pascal Koiran DP-Complete Problems Derived fromExtremalNP-Complete Properties Yi Cao, Joseph Culberson, and Lorna Stewart The Synchronization Problem for Locally Strongly Transitive Automata Arturo Carpi and Flavio D’Alessandro Constructing Brambles Mathieu Chapelle, Fr? ed? eric Mazoit, and Ioan Todinca Self-indexed TextCompression Using Straight-Line Programs Francisco Claude and Gonzalo Navarro Security and Tradeo?s ofthe Akl-Taylor Scheme and Its Variants Paolo D’Arco, Alfredo De Santis, Anna Lisa Ferrara, and Barbara Masucci Parameterized Complexity Classes under Logical Reductions Anuj Dawar and Yuguo He The Communication Complexityof Non-signaling Distributions Julien Degorre, Marc Kaplan, Sophie Laplante, and J?er?emie Roland How toUse Spanning Trees toNavigate in Graphs (Extended Abstract) Feodor F. Dragan and Yang Xiang RepresentingGroups on Graphs Sagarmoy Dutta and Piyush P. Kurur Admissible Strategies in In?nite Games over Graphs Marco Faella A ComplexityDichotomy for Finding Disjoint Solutions of Vertex Deletion Problems Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier Future-Looking Logics on Data Words and Trees Diego Figueira and Luc Segou?n ABy-LevelAnalysis of MultiplicativeExponentialLinear Logic Marco Gaboardi, Luca Roversi, and Luca Vercel li Hyper-minimisation Made E?cient Pawe l Gawrychowski and Artur Je?z Regular Expressions with Counting:Weak versus Strong Determinism Wouter Gelade, Marc Gyssens, and Wim Martens Choosabilityof P5-Free Graphs Petr A. Golovach and Pinar Heggernes Time-Bounded Kolmogorov Complexity and SolovayFunctions Rupert H? olzl, Thorsten Kr? aling, and Wolfgang Merkle The Longest Path Problem Is PolynomialonInterval Graphs Kyriaki Ioannidou, George B. Mertzios, and Stavros D. Nikolopoulos Synthesisfor Structure Rewriting Systems Lukasz Kaiser On the HybridExtension ofCTL andCTL+ Ahmet Kara, Volker Weber, Martin Lange, and Thomas Schwentick Bounds on Non-surjectiveCellular Automata Jarkko Kari, Pascal Vanier, and Thomas Zeume FO Model Checking on Nested Pushdown Trees Alexander Kartzow The Prismoid ofResources Delia Kesner and Fabien Renaud ADynamic Algorithm forReachability Games Played on Trees Bakhadyr Khoussainov, Jiamou Liu, and Imran Khaliq An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series IsRecognizable Daniel Kirsten Graph Decomposition for Improving Memoryless Periodic Exploration Adrian Kosowski and Alfredo Navarra On FO2 Quanti?er Alternation over Words Manfred Ku?eitner and Pascal Weil On the Recognizabilityof Self-generating Sets Tomi K? arki, Anne Lacroix, and Michel Rigo The Isomorphism Problem for k-Trees IsComplete for Logspace Johannes K? obler and Sebastian Kuhnert Snake-Deterministic Tiling Systems Violetta Lonati and Matteo Pradella QueryAutomata for Nested Words P. Madhusudan and Mahesh Viswanathan A General Class of Models of H? Giulio Manzonetto The Complexityof Satis?ability for Fragments of Hybrid Logic—Part I Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, and Felix Weiss Colouring Non-sparse Random Intersection Graphs . Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis On the Structure ofOptimal Greedy Computation (for Job Scheduling) Periklis A. Papakonstantinou AProbabilistic PTAS for Shortest Common Superstring Kai Plociennik The Cost of StabilityinNetwork Flow Games Ezra Resnick, Yoram Bachrach, Reshef Meir, and Je?rey S. Rosenschein (Un)Decidabilityof Injectivity and Surjectivityin One-Dimensional Sand Automata Ga?etan Richard Quantum Algorithms toSolvethe HiddenShift Problem for Quadratics andf or Functions of Large Gowers Norm Martin R?otteler From Parity and Payo? Games to Linear Programming Sven Schewe Partial Randomness and Dimension of Recursively EnumerableReals Kohtaro Tadaki PartialSolution and Entropy Tadao Takaoka OnPebble Automata for Data Languages with DecidableEmptiness Problem Tony Tan Size andEnergyof ThresholdCircuits Computing Mod Functions Kei Uchizawa, Takao Nishizeki, and Eiji Takimoto Points on ComputableCurves ofComputable Lengths Robert Rettinger and Xizhong Zheng The Expressive Power of BinarySubmodular Functions Stanislav ? Zivn? y, David A. Cohen, and Peter G. Jeavons Author Index
