FSTTCS 2014 December 15-17, 2014 - New Delhi, India

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)



Venkatesh Raman and S. P. Suresh (Eds.)
ISBN 978-3-939897-77-4, LIPICS Vol. 29 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 26 MB)
Search Publication Server

Authors
  • Abdulla, Parosh Aziz
  • Almagor, Shaull
  • Arora, Sonika
  • Atig, Mohamed Faouzi
  • Ayala-Rincón, Mauricio
  • Baldan, Paolo
  • Bansal, Nikhil
  • Basavaraju, Manu
  • Berkholz, Christoph
  • Bertrand, Nathalie
  • Biondi, Fabrizio
  • Bock, Adrian
  • Bollig, Benedikt
  • Bonchi, Filippo
  • Bouajjani, Ahmed
  • Bouyer, Patricia
  • Burnett, Karla
  • Cassez, Franck
  • Cem Say, A. C.
  • Chadha, Rohit
  • Chakaravarthy, Venkatesan T.
  • Chakraborty, Diptarka
  • Chastain, Erick
  • Chaudhuri, Kaustuv
  • Chen, Taolue
  • Chistikov, Dmitry
  • Colcombet, Thomas
  • Cyriac, Aiswarya
  • Dabrowski, Konrad K.
  • David, Claire
  • de Moura, Flávio L. C.
  • de Rugy-Altherre, Nicolas
  • Dhayal, Anant
  • Doyen, Laurent
  • Durand, Arnaud
  • Elberfeld, Michael
  • Faenza, Yuri
  • Fijalkow, Nathanael
  • Filiot, Emmanuel
  • Fomin, Fedor V.
  • Francis, Nadime
  • Gastin, Paul
  • Gelman, Efraim
  • Gentilini, Raffaella
  • Georgiou, Konstantinos
  • Giannopoulou, Archontia C.
  • Golovach, Petr A.
  • Grohe, Martin
  • Grossi, Roberto
  • Gupta, Kanika
  • Gupta, Manoj
  • Gupta, Neelima
  • Haddad, Serge
  • Han, Tingting
  • Har-Peled, Sariel
  • Henzinger, Thomas A.
  • Horn, Florian
  • Hucke, Danny
  • Hunter, Paul
  • Juhl, Line
  • Kara, Ahmet
  • Keil, Matthias
  • Kerstan, Henning
  • Kesner, Delia
  • Klauck, Hartmut
  • Krishna, Shankara Narayanan
  • Kumar, Akshay
  • Kumar, Nirman
  • Kuperberg, Denis
  • Kupferman, Orna
  • König, Barbara
  • Larsen, Kim G.
  • Lee, Edward
  • Lefaucheux, Engel
  • Legay, Axel
  • Livnat, Adi
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Mahajan, Meena
  • Malacaria, Pasquale
  • Malod, Guillaume
  • Mandal, Debasis
  • Manuel, Amaldev
  • Markey, Nicolas
  • Mathur, Umang
  • Menconi, Giulia
  • Moldenhauer, Carsten
  • Murlak, Filip
  • Muscholl, Anca
  • Müller, Christian
  • Narayan Kumar, K.
  • Navarro, Gonzalo
  • Nielsen, Bo Friis
  • Noeth, Eric
  • O'Donnell, Ryan
  • Otop, Jan
  • Papadimitriou, Christos H.
  • Paulusma, Daniel
  • Pavan, A.
  • Philip, Geevarghese
  • Pisanti, Nadia
  • Podder, Supartha
  • Raman, Rajeev
  • Raman, Venkatesh
  • Ramanujan, M. S.
  • Raskin, Jean-Francois
  • Rezine, Othmane
  • Ruiz-Vargas, Andres Jacinto
  • Sabharwal, Yogish
  • Saivasan, Prakash
  • Samanta, Roopsha
  • Sankur, Ocan
  • Sarma, Jayalal
  • Satti, Srinivasa Rao
  • Saurabh, Nitin
  • Saurabh, Saket
  • Sawlani, Saurabh
  • Schwoon, Stefan
  • Shirmohammadi, Mahsa
  • Song, Fu
  • Southern, Mary
  • Stan, Daniel
  • Suchy, Ondrej
  • Suresh, S. P.
  • Ta-Shma, Amnon
  • Tamir, Tami
  • Tewari, Raghunath
  • Thiemann, Peter
  • Torfah, Hazem
  • Trani, Roberto
  • Trivedi, Ashutosh
  • van 't Hof, Pim
  • Vazirani, Umesh V.
  • Venugopalan, Rajeswari
  • Vind, Soren
  • Vinodchandran, N. V.
  • Walukiewicz, Igor
  • Wasowski, Andrzej
  • Williams, Richard Ryan
  • Wu, Zhilin
  • Yang, Lin Forrest
  • Zimmermann, Martin
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Raman, Venkatesh ; Suresh, S. P.

    Abstract | Document (361 KB) | BibTeX

    New Developments in Iterated Rounding (Invited Talk)
    Authors: Bansal, Nikhil

    Abstract | Document (401 KB) | BibTeX

    Reasoning About Distributed Systems: WYSIWYG (Invited Talk)
    Authors: Cyriac, Aiswarya ; Gastin, Paul

    Abstract | Document (707 KB) | BibTeX

    Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk)
    Authors: Grohe, Martin

    Abstract | Document (204 KB) | BibTeX

    Properties and Utilization of Capacitated Automata (Invited Talk)
    Authors: Kupferman, Orna ; Tamir, Tami

    Abstract | Document (602 KB) | BibTeX

    Algorithms, Games, and Evolution (Invited Talk)
    Authors: Chastain, Erick ; Livnat, Adi ; Papadimitriou, Christos H. ; Vazirani, Umesh V.

    Abstract | Document (284 KB) | BibTeX

    The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)
    Authors: Williams, Richard Ryan

    Abstract | Document (456 KB) | BibTeX

    Vertex Exponential Algorithms for Connected f-Factors
    Authors: Philip, Geevarghese ; Ramanujan, M. S.

    Abstract | Document (443 KB) | BibTeX

    Connecting Vertices by Independent Trees
    Authors: Basavaraju, Manu ; Fomin, Fedor V. ; Golovach, Petr A. ; Saurabh, Saket

    Abstract | Document (551 KB) | BibTeX

    Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)
    Authors: Giannopoulou, Archontia C. ; Lokshtanov, Daniel ; Saurabh, Saket ; Suchy, Ondrej

    Abstract | Document (568 KB) | BibTeX

    Editing to Eulerian Graphs
    Authors: Dabrowski, Konrad K. ; Golovach, Petr A. ; van 't Hof, Pim ; Paulusma, Daniel

    Abstract | Document (522 KB) | BibTeX

    Parameterized Complexity of Fixed Variable Logics
    Authors: Berkholz, Christoph ; Elberfeld, Michael

    Abstract | Document (492 KB) | BibTeX

    Synchronizing Words for Weighted and Timed Automata
    Authors: Doyen, Laurent ; Juhl, Line ; Larsen, Kim G. ; Markey, Nicolas ; Shirmohammadi, Mahsa

    Abstract | Document (523 KB) | BibTeX

    Finite-Valued Weighted Automata
    Authors: Filiot, Emmanuel ; Gentilini, Raffaella ; Raskin, Jean-Francois

    Abstract | Document (484 KB) | BibTeX

    First-order Definable String Transformations
    Authors: Filiot, Emmanuel ; Krishna, Shankara Narayanan ; Trivedi, Ashutosh

    Abstract | Document (560 KB) | BibTeX

    Regular Sensing
    Authors: Almagor, Shaull ; Kuperberg, Denis ; Kupferman, Orna

    Abstract | Document (483 KB) | BibTeX

    Symbolic Solving of Extended Regular Expression Inequalities
    Authors: Keil, Matthias ; Thiemann, Peter

    Abstract | Document (449 KB) | BibTeX

    Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number
    Authors: Bock, Adrian ; Faenza, Yuri ; Moldenhauer, Carsten ; Ruiz-Vargas, Andres Jacinto

    Abstract | Document (400 KB) | BibTeX

    Lift & Project Systems Performing on the Partial Vertex Cover Polytope
    Authors: Georgiou, Konstantinos ; Lee, Edward

    Abstract | Document (504 KB) | BibTeX

    Replica Placement on Directed Acyclic Graphs
    Authors: Arora, Sonika ; Chakaravarthy, Venkatesan T. ; Gupta, Kanika ; Gupta, Neelima ; Sabharwal, Yogish

    Abstract | Document (915 KB) | BibTeX

    Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time
    Authors: Gupta, Manoj

    Abstract | Document (552 KB) | BibTeX

    The Complexity of Counting Models of Linear-time Temporal Logic
    Authors: Torfah, Hazem ; Zimmermann, Martin

    Abstract | Document (507 KB) | BibTeX

    Extending Temporal Logics with Data Variable Quantifications
    Authors: Song, Fu ; Wu, Zhilin

    Abstract | Document (581 KB) | BibTeX

    Generalized Data Automata and Fixpoint Logic
    Authors: Colcombet, Thomas ; Manuel, Amaldev

    Abstract | Document (477 KB) | BibTeX

    Consistency of Injective Tree Patterns
    Authors: David, Claire ; Francis, Nadime ; Murlak, Filip

    Abstract | Document (495 KB) | BibTeX

    Asymptotically Optimal Encodings for Range Selection
    Authors: Navarro, Gonzalo ; Raman, Rajeev ; Satti, Srinivasa Rao

    Abstract | Document (475 KB) | BibTeX

    Output-Sensitive Pattern Extraction in Sequences
    Authors: Grossi, Roberto ; Menconi, Giulia ; Pisanti, Nadia ; Trani, Roberto ; Vind, Soren

    Abstract | Document (566 KB) | BibTeX

    Robust Proximity Search for Balls Using Sublinear Space
    Authors: Har-Peled, Sariel ; Kumar, Nirman

    Abstract | Document (511 KB) | BibTeX

    The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent
    Authors: Gelman, Efraim ; Ta-Shma, Amnon

    Abstract | Document (544 KB) | BibTeX

    Notes on Counting with Finite Machines
    Authors: Chistikov, Dmitry

    Abstract | Document (470 KB) | BibTeX

    Mixed Nash Equilibria in Concurrent Terminal-Reward Games
    Authors: Bouyer, Patricia ; Markey, Nicolas ; Stan, Daniel

    Abstract | Document (471 KB) | BibTeX

    Quantitative Games with Interval Objectives
    Authors: Hunter, Paul ; Raskin, Jean-Francois

    Abstract | Document (553 KB) | BibTeX

    Playing Safe
    Authors: Colcombet, Thomas ; Fijalkow, Nathanael ; Horn, Florian

    Abstract | Document (455 KB) | BibTeX

    Metaconfluence of Calculi with Explicit Substitutions at a Distance
    Authors: de Moura, Flávio L. C. ; Kesner, Delia ; Ayala-Rincón, Mauricio

    Abstract | Document (462 KB) | BibTeX

    Behavioral Metrics via Functor Lifting
    Authors: Baldan, Paolo ; Bonchi, Filippo ; Kerstan, Henning ; König, Barbara

    Abstract | Document (542 KB) | BibTeX

    Foundation of Diagnosis and Predictability in Probabilistic Systems
    Authors: Bertrand, Nathalie ; Haddad, Serge ; Lefaucheux, Engel

    Abstract | Document (506 KB) | BibTeX

    Lipschitz Robustness of Finite-state Transducers
    Authors: Henzinger, Thomas A. ; Otop, Jan ; Samanta, Roopsha

    Abstract | Document (549 KB) | BibTeX

    Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis
    Authors: Mandal, Debasis ; Pavan, A. ; Venugopalan, Rajeswari

    Abstract | Document (437 KB) | BibTeX

    Constructing Small Tree Grammars and Small Circuits for Formulas
    Authors: Hucke, Danny ; Lohrey, Markus ; Noeth, Eric

    Abstract | Document (481 KB) | BibTeX

    One Time-traveling Bit is as Good as Logarithmically Many
    Authors: O'Donnell, Ryan ; Cem Say, A. C.

    Abstract | Document (517 KB) | BibTeX

    New Bounds for the Garden-Hose Model
    Authors: Klauck, Hartmut ; Podder, Supartha

    Abstract | Document (459 KB) | BibTeX

    Homomorphism Polynomials Complete for VP
    Authors: Durand, Arnaud ; Mahajan, Meena ; Malod, Guillaume ; de Rugy-Altherre, Nicolas ; Saurabh, Nitin

    Abstract | Document (509 KB) | BibTeX

    Computing Information Flow Using Symbolic Model-Checking
    Authors: Chadha, Rohit ; Mathur, Umang ; Schwoon, Stefan

    Abstract | Document (566 KB) | BibTeX

    Information Leakage of Non-Terminating Processes
    Authors: Biondi, Fabrizio ; Legay, Axel ; Nielsen, Bo Friis ; Malacaria, Pasquale ; Wasowski, Andrzej

    Abstract | Document (631 KB) | BibTeX

    Multiple-Environment Markov Decision Processes
    Authors: Raskin, Jean-Francois ; Sankur, Ocan

    Abstract | Document (520 KB) | BibTeX

    Summary-Based Inter-Procedural Analysis via Modular Trace Refinement
    Authors: Cassez, Franck ; Müller, Christian ; Burnett, Karla

    Abstract | Document (642 KB) | BibTeX

    A Two-Level Logic Approach to Reasoning About Typed Specification Languages
    Authors: Southern, Mary ; Chaudhuri, Kaustuv

    Abstract | Document (553 KB) | BibTeX

    On the Complexity of Computing Maximum Entropy for Markovian Models
    Authors: Chen, Taolue ; Han, Tingting

    Abstract | Document (458 KB) | BibTeX

    New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs
    Authors: Chakraborty, Diptarka ; Pavan, A. ; Tewari, Raghunath ; Vinodchandran, N. V. ; Yang, Lin Forrest

    Abstract | Document (468 KB) | BibTeX

    Polynomial Min/Max-weighted Reachability is in Unambiguous Log-space
    Authors: Dhayal, Anant ; Sarma, Jayalal ; Sawlani, Saurabh

    Abstract | Document (477 KB) | BibTeX

    On Bounded Reachability Analysis of Shared Memory Systems
    Authors: Atig, Mohamed Faouzi ; Bouajjani, Ahmed ; Narayan Kumar, K. ; Saivasan, Prakash

    Abstract | Document (507 KB) | BibTeX

    Parameterized Communicating Automata: Complementation and Model Checking
    Authors: Bollig, Benedikt ; Gastin, Paul ; Kumar, Akshay

    Abstract | Document (1,105 KB) | BibTeX

    Distributed Synthesis for Acyclic Architectures
    Authors: Muscholl, Anca ; Walukiewicz, Igor

    Abstract | Document (2,520 KB) | BibTeX

    Verification of Dynamic Register Automata
    Authors: Abdulla, Parosh Aziz ; Atig, Mohamed Faouzi ; Kara, Ahmet ; Rezine, Othmane

    Abstract | Document (599 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI