FSTTCS 2011 December 12-14, 2011, Mumbai, India

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)



Supratik Chakraborty and Amit Kumar (Eds.)
ISBN 978-3-939897-34-7, LIPICS Vol. 13 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 18 MB)
Search Publication Server

Support
  • IARCS

    • Authors
  • Adiga, Abhijin
  • Albers, Susanne
  • Ananth, Prabhanjan
  • Atig, Mohamed Faouzi
  • Bain, Alex
  • Barceló, Pablo
  • Ben-Kiki, Oren
  • Benabbas, Siavosh
  • Bertrand, Nathalie
  • Berwanger, Dietmar
  • Bille, Philip
  • Bouyer, Patricia
  • Brenguier, Romain
  • Breslauer, Dany
  • Bruggink, H. J. Sander
  • Cai, Yang
  • Caminiti, Saverio
  • Caucal, Didier
  • Cauderlier, Raphaël
  • Chakraborty, Supratik
  • Chan, Siu On
  • Chandran, L. Sunil
  • Chevalier, Céline
  • Crowston, Robert
  • Cygan, Marek
  • Darondeau, Philippe
  • Delaune, Stéphanie
  • Demri, Stéphane
  • Duparc, Jacques
  • Durand, Arnaud
  • Ebbing, Johannes
  • Facchini, Alessandro
  • Fahrenberg, Uli
  • Fearnley, John
  • Felgenhauer, Bertram
  • Fellows, Michael
  • Filiot, Emmanuel
  • Finocchi, Irene
  • Fomin, Fedor V.
  • Fu, Hongfei
  • Fusco, Emanuele G.
  • Ganty, Pierre
  • Gasieniec, Leszek
  • Gauwin, Olivier
  • Genest, Blaise
  • Georgiou, Konstantinos
  • Glaßer, Christian
  • Grandoni, Fabrizio
  • Grenet, Bruno
  • Grossi, Roberto
  • Gupta, Manoj
  • Gutin, Gregory
  • Göller, Stefan
  • Hague, Matthew
  • Heggernes, Pinar
  • Herbreteau, Frédéric
  • Hülsbusch, Mathias
  • Jones, Mark
  • Kaiser, Lukasz
  • Katoen, Joost-Pieter
  • Kieronski, Emanuel
  • Kini, Dileep
  • Knapik, Teodor
  • Koiran, Pascal
  • Kolaitis, Phokion G.
  • Kontinen, Juha
  • Kremer, Steve
  • Kumar, Amit
  • Kuperberg, Denis
  • König, Barbara
  • Legay, Axel
  • Leonardi, Stefano
  • Libkin, Leonid
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Madry, Aleksander
  • Magen, Avner
  • Markey, Nicolas
  • Mathew, Rogers
  • Meyer, Roland
  • Michaliszyn, Jakub
  • Middeldorp, Aart
  • Mitchell, John
  • Morvan, Christophe
  • Mucha, Marcin
  • Murlak, Filip
  • Nasre, Meghana
  • Otop, Jan
  • Panigrahi, Debmalya
  • Paul, Christophe
  • Philip, Geevarghese
  • Pilipczuk, Marcin
  • Portier, Natacha
  • Puchala, Bernd
  • Rabe, Markus
  • Rao B .V., Raghavendra
  • Reitwießner, Christian
  • Reutter, Juan L.
  • Reynier, Pierre-Alain
  • Rosamond, Frances
  • Sabharwal, Yogish
  • Sankowski, Piotr
  • Sankur, Ocan
  • Sarma M. N. , Jayalal
  • Sarpatwar, Kanthi K.
  • Schewe, Sven
  • Sen, Sandeep
  • Servais, Frédéric
  • Sharma, Rahul
  • Silvestri, Francesco
  • Srivathsan, B.
  • Stefan, Deian
  • Strozecki, Yann
  • Sudan, Madhu
  • Thomassé, Stéphan
  • Thrane, Claus
  • Ummels, Michael
  • van 't Hof, Pim
  • Vanden Boom, Michael
  • Vardi, Moshe Y.
  • Vazirani, Umesh V.
  • Villanger, Yngve
  • Vollmer, Heribert
  • Walukiewicz, Igor
  • Weimann, Oren
  • Witek, Maximilian
  • Yeo, Anders
  • Zankl, Harald
  • Zhang, Lijun
  • Zhang, Ting
  • Zimmerman, Joe
    		•

    		  
    Frontmatter, Table of Contents, Preface, Conference Organization, External Reviewers
    Authors: Chakraborty, Supratik ; Kumar, Amit

    Abstract | Document (316 KB) | BibTeX

    Author Index
    Authors: Chakraborty, Supratik ; Kumar, Amit

    Abstract | Document (107 KB) | BibTeX

    Energy-Efficient Algorithms (Invited Talk)
    Authors: Albers, Susanne

    Abstract | Document (250 KB) | BibTeX

    Constraints, Graphs, Algebra, Logic, and Complexity (Invited Talk)
    Authors: Vardi, Moshe Y.

    Abstract | Document (244 KB) | BibTeX

    Physical limits of Communication (Invited Talk)
    Authors: Sudan, Madhu

    Abstract | Document (219 KB) | BibTeX

    A Domain-Specific Language for Computing on Encrypted Data (Invited Talk)
    Authors: Bain, Alex ; Mitchell, John ; Sharma, Rahul ; Stefan, Deian ; Zimmerman, Joe

    Abstract | Document (604 KB) | BibTeX

    Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk)
    Authors: Kolaitis, Phokion G.

    Abstract | Document (218 KB) | BibTeX

    Quantum State Description Complexity (Invited Talk)
    Authors: Vazirani, Umesh V.

    Abstract | Document (268 KB) | BibTeX

    Approximation Algorithms for Union and Intersection Covering Problems
    Authors: Cygan, Marek ; Grandoni, Fabrizio ; Leonardi, Stefano ; Mucha, Marcin ; Pilipczuk, Marcin ; Sankowski, Piotr

    Abstract | Document (511 KB) | BibTeX

    Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy
    Authors: Benabbas, Siavosh ; Chan, Siu On ; Georgiou, Konstantinos ; Magen, Avner

    Abstract | Document (584 KB) | BibTeX

    Applications of Discrepancy Theory in Multiobjective Approximation
    Authors: Glaßer, Christian ; Reitwießner, Christian ; Witek, Maximilian

    Abstract | Document (421 KB) | BibTeX

    Quasi-Weak Cost Automata: A New Variant of Weakness
    Authors: Kuperberg, Denis ; Vanden Boom, Michael

    Abstract | Document (443 KB) | BibTeX

    Using non-convex approximations for efficient analysis of timed automata
    Authors: Herbreteau, Frédéric ; Kini, Dileep ; Srivathsan, B. ; Walukiewicz, Igor

    Abstract | Document (546 KB) | BibTeX

    Shrinking Timed Automata
    Authors: Sankur, Ocan ; Bouyer, Patricia ; Markey, Nicolas

    Abstract | Document (498 KB) | BibTeX

    The Quantitative Linear-Time--Branching-Time Spectrum
    Authors: Fahrenberg, Uli ; Legay, Axel ; Thrane, Claus

    Abstract | Document (414 KB) | BibTeX

    Isomorphism testing of read-once functions and polynomials
    Authors: Rao B .V., Raghavendra ; Sarma M. N. , Jayalal

    Abstract | Document (396 KB) | BibTeX

    The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent
    Authors: Grenet, Bruno ; Koiran, Pascal ; Portier, Natacha ; Strozecki, Yann

    Abstract | Document (454 KB) | BibTeX

    Petri Net Reachability Graphs: Decidability Status of FO Properties
    Authors: Darondeau, Philippe ; Demri, Stéphane ; Meyer, Roland ; Morvan, Christophe

    Abstract | Document (513 KB) | BibTeX

    Approximating Petri Net Reachability Along Context-free Traces
    Authors: Atig, Mohamed Faouzi ; Ganty, Pierre

    Abstract | Document (561 KB) | BibTeX

    Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
    Authors: Fomin, Fedor V. ; Philip, Geevarghese ; Villanger, Yngve

    Abstract | Document (522 KB) | BibTeX

    Cubicity, Degeneracy, and Crossing Number
    Authors: Adiga, Abhijin ; Chandran, L. Sunil ; Mathew, Rogers

    Abstract | Document (444 KB) | BibTeX

    Conditional Reactive Systems
    Authors: Bruggink, H. J. Sander ; Cauderlier, Raphaël ; Hülsbusch, Mathias ; König, Barbara

    Abstract | Document (561 KB) | BibTeX

    Transforming Password Protocols to Compose
    Authors: Chevalier, Céline ; Delaune, Stéphanie ; Kremer, Steve

    Abstract | Document (402 KB) | BibTeX

    Obtaining a Bipartite Graph by Contracting Few Edges
    Authors: Heggernes, Pinar ; van 't Hof, Pim ; Lokshtanov, Daniel ; Paul, Christophe

    Abstract | Document (482 KB) | BibTeX

    Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
    Authors: Crowston, Robert ; Fellows, Michael ; Gutin, Gregory ; Jones, Mark ; Rosamond, Frances ; Thomassé, Stéphan ; Yeo, Anders

    Abstract | Document (502 KB) | BibTeX

    Rainbow Connectivity: Hardness and Tractability
    Authors: Ananth, Prabhanjan ; Nasre, Meghana ; Sarpatwar, Kanthi K.

    Abstract | Document (407 KB) | BibTeX

    Dependence logic with a majority quantifier
    Authors: Durand, Arnaud ; Ebbing, Johannes ; Kontinen, Juha ; Vollmer, Heribert

    Abstract | Document (532 KB) | BibTeX

    Modal Logics Definable by Universal Three-Variable Formulas
    Authors: Kieronski, Emanuel ; Michaliszyn, Jakub ; Otop, Jan

    Abstract | Document (728 KB) | BibTeX

    The First-Order Theory of Ground Tree Rewrite Graphs
    Authors: Göller, Stefan ; Lohrey, Markus

    Abstract | Document (531 KB) | BibTeX

    Layer Systems for Proving Confluence
    Authors: Felgenhauer, Bertram ; Zankl, Harald ; Middeldorp, Aart

    Abstract | Document (575 KB) | BibTeX

    The Semi-stochastic Ski-rental Problem
    Authors: Madry, Aleksander ; Panigrahi, Debmalya

    Abstract | Document (455 KB) | BibTeX

    Streamability of Nested Word Transductions
    Authors: Filiot, Emmanuel ; Gauwin, Olivier ; Reynier, Pierre-Alain ; Servais, Frédéric

    Abstract | Document (590 KB) | BibTeX

    The update complexity of selection and related problems
    Authors: Gupta, Manoj ; Sabharwal, Yogish ; Sen, Sandeep

    Abstract | Document (532 KB) | BibTeX

    A Tight Lower Bound for Streett Complementation
    Authors: Cai, Yang ; Zhang, Ting

    Abstract | Document (481 KB) | BibTeX

    Parameterized Regular Expressions and Their Languages
    Authors: Barceló, Pablo ; Libkin, Leonid ; Reutter, Juan L.

    Abstract | Document (466 KB) | BibTeX

    Definable Operations On Weakly Recognizable Sets of Trees
    Authors: Duparc, Jacques ; Facchini, Alessandro ; Murlak, Filip

    Abstract | Document (608 KB) | BibTeX

    Nash Equilibria in Concurrent Games with Büchi Objectives
    Authors: Bouyer, Patricia ; Brenguier, Romain ; Markey, Nicolas ; Ummels, Michael

    Abstract | Document (458 KB) | BibTeX

    A Perfect-Information Construction for Coordination in Games
    Authors: Berwanger, Dietmar ; Kaiser, Lukasz ; Puchala, Bernd

    Abstract | Document (437 KB) | BibTeX

    Efficient Approximation of Optimal Control for Continuous-Time Markov Games
    Authors: Fearnley, John ; Rabe, Markus ; Schewe, Sven ; Zhang, Lijun

    Abstract | Document (579 KB) | BibTeX

    Minimal Disclosure in Partially Observable Markov Decision Processes
    Authors: Bertrand, Nathalie ; Genest, Blaise

    Abstract | Document (450 KB) | BibTeX

    Optimal Packed String Matching
    Authors: Ben-Kiki, Oren ; Bille, Philip ; Breslauer, Dany ; Gasieniec, Leszek ; Grossi, Roberto ; Weimann, Oren

    Abstract | Document (478 KB) | BibTeX

    Dynamic programming in faulty memory hierarchies (cache-obliviously)
    Authors: Caminiti, Saverio ; Finocchi, Irene ; Fusco, Emanuele G. ; Silvestri, Francesco

    Abstract | Document (509 KB) | BibTeX

    Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems
    Authors: Fu, Hongfei ; Katoen, Joost-Pieter

    Abstract | Document (420 KB) | BibTeX

    Parameterised Pushdown Systems with Non-Atomic Writes
    Authors: Hague, Matthew

    Abstract | Document (396 KB) | BibTeX

    Higher order indexed monadic systems
    Authors: Caucal, Didier ; Knapik, Teodor

    Abstract | Document (463 KB) | BibTeX

    		  



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