Springer, 2009. 760 р. ISSN 0302-9743 (на английском языке)
34 th Inteational 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 Ho
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 Do
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
Bed 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 Loa 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 Heggees
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 Alteation 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
Ae 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
34 th Inteational 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 Ho
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 Do
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
Bed 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 Loa 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 Heggees
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 Alteation 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
Ae 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