Erzsébet Csuhaj-Varjú Martin Dietzfelbinger Zoltán Ésik (Eds.) S S o C R A Mathematical 4 3 Foundations of 6 8 S C Computer Science 2014 N L 39th International Symposium, MFCS 2014 Budapest, Hungary, August 25-29, 2014 Proceedings, Part I 123 Lecture Notes in Computer Science 8634 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Erzsébet Csuhaj-Varjú Martin Dietzfelbinger Zoltán Ésik (Eds.) Mathematical Foundations of Computer Science 2014 39th International Symposium, MFCS 2014 Budapest, Hungary, August 25-29, 2014 Proceedings, Part I 1 3 VolumeEditors ErzsébetCsuhaj-Varjú EötvösLorándUniversity FacultyofInformatics Budapest,Hungary E-mail:[email protected] MartinDietzfelbinger TechnischeUniversitätIlmenau FakultätfürInformatikundAutomatisierung Ilmenau,Germany E-mail:[email protected] ZoltánÉsik SzegedUniversity InstituteofInformatics Szeged,Hungary E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-662-44521-1 e-ISBN978-3-662-44522-8 DOI10.1007/978-3-662-44522-8 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2014945809 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagGmbHBerlinHeidelberg2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthePublisher’slocation, inistcurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Permissionsforuse maybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violationsareliabletoprosecution undertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface The series of MFCS symposia has a long and well-established tradition. The MFCS conferences encourage high-quality research into all branches of theo- retical computer science. Their broad scope provides an opportunity to bring together researchers who do not usually meet at specialized conferences. The first symposium was held in 1972. Until 2012 MFCS symposia were organized on a rotating basis in Poland, the Czech Republic, and Slovakia. The 2013 edi- tiontookplaceinAustria,andin2014Hungaryjoinedtheorganizingcountries. The 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014) was held in Budapest during August 25–29, 2014. Duetothelargenumberofacceptedpapers,theproceedingsoftheconference weredividedintotwovolumesonathematicalbasis:Logic,Semantics,Automata and Theory of Programming (Vol. I) and Algorithms, Complexity and Games (Vol. II). The 95 contributed papers were selected by the Program Committee (PC)outofatotalof270submissions.All submittedpaperswerepeerreviewed and evaluated on the basis of originality, quality, significance, and presentation byatleastthreePCmemberswiththehelpofexternalexperts.ThePCdecided to give the BestPaperAward, sponsoredby the EuropeanAssociationof Theo- retical Computer Science (EATCS), to the paper“Zero Knowledge and Circuit Minimization”writtenbyEricAllenderandBireswarDas.Inaddition,thepaper entitled“The Dynamic Descriptive Complexity of k-Clique”by Thomas Zeume earned the Best Student Paper Award. The scientific programof the symposium included seven invited talks by: – Krishnendu Chatterjee (IST Austria, Klosterneuburg, Austria) – Achim Jung (University of Birmingham, UK) – D´aniel Marx (MTA SZTAKI, Hungary) – Peter Bro Miltersen (Aarhus University, Denmark) – Cyril Nicaud (Universit´e Paris-EstMarne-la-Vall´e, France) – Alexander Sherstov (University of California, Los Angeles, USA) – Christian Sohler (Technische Universit¨at Dortmund, Germany) We are grateful to all invited speakers for accepting our invitation and for their excellent presentations at the symposium. We thank all authors who sub- mitted their work for consideration to MFCS 2014. We deeply appreciate the competent and timely handling of the submissions of all PC members and ex- ternal reviewers. The members of the Organizing Committee were Erzs´ebet Csuhaj-Varju´ (chair, Budapest), Zsolt Gazdag (Budapest), Katalin Anna L´az´ar (Budapest) and Krisztia´n Tichler (Budapest). The website design and maintenance were carried out by Zolta´n L. N´emeth (University of Szeged). The publicity chair was Szabolcs Iva´n (University of Szeged). VI Preface The editors express their gratitude to Zsolt Gazdag, Katalin Anna La´z´ar, and Krisztia´n Tichler for their valuable contribution to the technical edition of the two volumes of proceedings. We thank Andrej Voronkov for his EasyChair system, which facilitated the work of the PC and the editors considerably. June 2014 Erzs´ebet Csuhaj-Varju´ Martin Dietzfelbinger Zolta´n E´sik Conference Organization The organization of the scientific part of the conference was supported by the Faculty of Informatics, E¨otv¨os Lora´nd University, Budapest, and the Institute of Computer Science, Faculty of Science and Informatics, University of Szeged. Some parts of the local arrangements were taken care of by the ELTE-Soft Non-Profit Organizationand Pannonia Tourist Service. Program Committee Chairs Zolta´n E´sik, chair University of Szeged, Hungary Erzs´ebet Csuhaj-Varju´, co-chair E¨otv¨os Lora´nd University, Hungary Martin Dietzfelbinger, co-chair Technische Universit¨at Ilmenau, Germany Program Committee Albert Atserias Technical University of Catalonia, Spain Giorgio Ausiello Sapienza University of Rome, Italy Jos Baeten CWI, The Netherlands Therese Biedl University of Waterloo, Canada Miko(cid:2)laj Bojan´czyk University of Warsaw, Poland Gerth Stølting Brodal Aarhus University, Denmark Christian Choffrut Paris Diderot University, France Rocco De Nicola IMT Institute for Advanced Studies Lucca, Italy Manfred Droste Leipzig University, Germany Robert Els¨asser University of Salzburg, Austria Uli Fahrenberg IRISA/Inria Rennes, France Fedor V. Fomin University of Bergen, Norway Fabio Gadducci University of Pisa, Italy Anna Ga´l The University of Texas at Austin, USA Dora Giammarresi University of Tor Vergata, Rome, Italy VIII Conference Organization Roberto Grossi University of Pisa, Italy Anupam Gupta Carnegie Mellon University, USA Michel Habib Paris Diderot University, France Kristoffer Arnsfelt Hansen Aarhus University, Denmark Edith Hemaspaandra Rochester Institute of Technology, USA Kazuo Iwama Kyoto University, Japan Yoshihiko Kakutani The University of Tokyo, Japan Juhani Karhum¨aki University of Turku, Finland Bakhadyr Khoussainov University of Auckland, New Zealand Elias Koutsoupias University of Oxford, UK Jan Kratochv´ıl Charles University, Prague, Czech Republic Stefan Kratsch Technical University of Berlin, Germany Rastislav Kr´aloviˇc Comenius University in Bratislava, Slovakia Amit Kumar Indian Institute of Technology Delhi, India Kim G. Larsen Aalborg University, Denmark Fr´ed´eric Magniez Paris Diderot University, France Ralph Matthes IRIT (CNRS and University of Toulouse), France Madhavan Mukund Chennai Mathematical Institute, India Jean-E´ric Pin LIAFA CNRS and Paris Diderot University, France Alexander Rabinovich Tel Aviv University, Israel Peter Rossmanith RWTH Aachen University, Germany Jan Rutten CWI and Radboud University Nijmegen, The Netherlands Wojciech Rytter Warsaw University and Copernicus University in Torun, Poland Luigi Santocanale Aix-Marseille University, France Christian Scheideler University of Paderborn, Germany Thomas Schwentick TU Dortmund University, Germany Alex Simpson University of Edinburgh, UK Mohit Singh Microsoft Research Redmond, USA Klaus Sutner Carnegie Mellon University, USA Ga´bor Tardos R´enyi Institute, Hungary Gy¨orgy Tura´n University of Illinois at Chicago, USA Peter Widmayer ETH Zu¨rich, Switzerland Philipp Woelfel University of Calgary, Canada Steering Committee Juraj Hromkoviˇc ETH Zu¨rich, Switzerland Anton´ın Kuˇcera (Chair) Masaryk University, Czech Republic Jerzy Marcinkowski University of Wroc(cid:2)law, Poland Damian Niwinski University of Warsaw, Poland Branislav Rovan Comenius University in Bratislava, Slovakia Jiˇr´ı Sgall Charles University, Prague, Czech Republic Conference Organization IX Additional Reviewers Abel, Andreas Buss, Sam Facchini, Alessandro Aceto, Luca Cal`ı, Andrea Faliszewski, Piotr Acher, Mathieu Carayol, Arnaud Feldmann, Andreas Emil Aghazadeh, Zahra Carpi, Arturo Fernau, Henning Ahrens, Benedikt Caucal, Didier Ferreira, Francisco Allender, Eric Cechl´arova´, Katar´ına Fertin, Guillaume Ambos-Spies, Klaus Chang, Richard Fici, Gabriele Andrews, Matthew Christophe, Reutenauer Finocchi, Irene Anselmo, Marcella Chroboczek, Juliusz Firmani, Donatella Bacci, Giorgio Colcombet, Thomas Fitzsimmons, Zack Bacci, Giovanni Colin de Verdi`ere, E´ric Forisek, Michal Baertschi, Andreas Cook, Stephen Fortier, J´erˆome Balbiani, Philippe Cosme Ll´opez, Enric Forys, Wit Barcelo´, Pablo Cranen, Sjoerd Fournier, Herv´e Bartha, Mikl´os Crescenzi, Pierluigi Fran¸cois, Nathana¨el Barto, Libor Crespi Reghizzi, Stefano Fratani, S´everine Basavaraju,Manu Cyriac, Aiswarya Fredriksson, Kimmo Basold, Henning Czeizler, Elena Freivalds, Rusins Baumeister, Dorothea D’Alessandro, Flavor Frid, Anna B´eal, Marie-Pierre D’Souza, Deepak Frigioni, Daniele Ben-Amram, Amir Dalmau, Victor Frougny, Christiane Berenbrink, Petra Damaschke, Peter Fusy, E´ric Berth´e, Val´erie Datta, Samir Gairing, Martin Bil`o, Davide de Boysson, Marianne Gasieniec, Leszek Bil`o, Vittorio de Mesmay, Arnaud Gaspers, Serge Blanchet-Sadri, Francine de Rougemont, Michel Gastin, Paul Bliznets, Ivan de Wolf, Ronald Gavalda, Ricard Boasson, Luc Dell, Holger Gawrychowski, Pawel Bodlaender, Hans L. Demetrescu, Camil Gharibian, Sevag B¨ohmova, Katerina Diekert, Volker Giustolisi, Rosario Bollig, Benedikt Dinneen, Michael Gliozzi, Valentina Bonchi, Filippo Drange, P˚al Grøn˚as Gmyr, Robert Bonelli, Eduardo Dube, Simant Goldwurm, Massimiliano Bonfante, Guillaume Du¨ck, Stefan Golovach, Petr Bonifaci, Vincenzo Du¨rr, Christoph Grigorieff, Serge Bonsma, Paul Duparc, Jacques Gual`a, Luciano Boudjadar, A.Jalil Durand, Arnaud Guillon, Bruno Bozzelli, Laura Eikel, Martina Gupta, Sushmita Breveglieri, Luca Elahi, Maryam Habermehl, Peter Brinkmann, Andr´e Elbassioni, Khaled Harju, Tero Broadbent, Christopher Elberfeld, Michael Hatami, Pooya Brotherston, James Epifanio, Chiara Hellerstein, Lisa Brunet, Paul Esp´ırito Santo, Jos´e Hemaspaandra, Lane A. X Conference Organization Henglein, Fritz Kosowski, Adrian Martin, Barnaby Hertrampf, Ulrich Koutris, Paraschos Marx, D´aniel Hill, Cameron Koutsopoulos, Andreas Mathieson, Luke Hirvensalo, Mika Kr´aloviˇc, Richard Matouˇsek, Jiˇr´ı Holzer, Stephan Kratsch, Dieter Maudet, Nicolas Honda, Kentaro Krebs, Andreas Mayr, Richard Horn, Florian Krokhin, Andrei Mendler, Michael Hovland, Dag Kˇretinsky´, Jan Mihal’´ak, Matu´ˇs Huang, Chien-Chung Kuˇcera, Petr Mikulski, Lukasz Huang, Sangxia Kufleitner, Manfred Mio, Matteo Huang, Zhiyi Kuhnert, Sebastian Miyazaki, Shuichi Huber, Stefan Kuperberg, Denis Momigliano, Alberto Hung, Ling-Ju Kutrib, Martin Monmege, Benjamin Hyvernat, Pierre Kuznets, Roman Montanari, Sandro Imreh, Csan´ad La Torre, Salvatore Morton, Jason Inaba, Kazuhiro Labarre, Anthony Mouawad, Amer Iva´n, Szabolcs Labb´e, S´ebastien Mu¨hlenthaler, Moritz Ivanyos, G´abor Labella, Anna Mu¨ller, Moritz Jancar, Petr Ladra, Susana Nagy-Gy¨orgy, Judit Jansen, Bart M.P. Laura, Luigi Narayanaswamy,N.S. Jansen, Klaus Le Gall, Franc¸ois Nederlof, Jesper Jeˇr´abek, Emil Lecroq, Thierry Negri, Sara Kaaser, Dominik Leroy, Julien Neven, Frank Kabanets, Valentine Liaghat, Vahid Nichterlein, Andr´e Kaminski, Michael Limouzy, Vincent Niewerth, Matthias Kamin´ski, Marcin Liu, Jiamou Nishimura, Naomi Kant´e, Mamadou Lluch Lafuente, Alberto Nisse, Nicolas Moustapha Lodaya, Kamal Niwinski, Damian Kara, Ahmet Lohrey, Markus Nonner, Tim Kari, Jarkko Lokshtanov, Daniel Nyman, Ulrik Kawamoto, Yusuke Lombardy, Sylvain Ochremiak, Joanna Kerenidis, Iordanis Lomonaco, Sam Okhotin, Alexander Kieronski, Emanuel Lonati, Violetta Olesen, Mads Chr. Kimura, Daisuke Loreti, Michele Ouaknine, Jo¨el Klasing, Ralf Lubiw, Anna Palfrader, Peter Klein, Philip Luttik, Bas Pandey, Omkant Klimann, Ines Madelaine, Florent Panella, Federica Klin, Bartek Madonia, Maria Paperman, Charles Kling, Peter Malcher, Andreas Parberry, Ian Kniesburges, Sebastian Maletti, Andreas Pardubska, Dana Kociumaka, Tomasz Mamageishvili, Akaki Parekh, Ojas Kollias, Konstantinos Mamcarz, Antoine Paulusma, Daniel Komm, Dennis Manlove, David Pavan, Aduri Konrad, Christian Markovski, Jasen Perevoshchikov,Vitaly Kontchakov,Roman Martens, Wim Perrin, Dominique