FSTTCS 2010 December 15-18, 2010, Chennai, India

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



Kamal Lodaya and Meena Mahajan (Eds.)
ISBN 978-3-939897-23-1, LIPICS Vol. 8 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 18 MB)
Search Publication Server

Support
  • IARCS

    • Authors
  • Akshay, S.
  • Alur, Rajeev
  • Arvind, V.
  • Asarin, Eugene
  • Atig, Mohamed Faouzi
  • Backes, Michael
  • Berman, Piotr
  • Boker, Udi
  • Bonchi, Filippo
  • Bonnet, Rémi
  • Bonsangue, Marcello M.
  • Bouyer, Patricia
  • Brázdil, Tomás
  • Brozek, Václav
  • Capecchi, Sara
  • Černý, Pavol
  • Chadha, Rohit
  • Chailloux, André
  • Chakaravarthy, Venkatesan T.
  • Chakraborty, Sourav
  • Chatterjee, Krishnendu
  • Chattopadhyay, Arkadev
  • Choudhury, Anamitra R.
  • Courcelle, Bruno
  • Czerwinski, Wojciech
  • Da Costa, Arnaud
  • Das, Bireswar
  • Degorre, Aldric
  • de Wolf, Ronald
  • Doyen, Laurent
  • Etessami, Kousha
  • Fellows, Michael
  • Finkel, Alain
  • Fischer, Eldar
  • Ganian, Robert
  • Gastin, Paul
  • Genest, Blaise
  • Ge, Qi
  • Giachino, Elena
  • Goel, Gagan
  • Hague, Matthew
  • Henzinger, Thomas A.
  • Hlinený, Petr
  • Hunter, Paul
  • Jansen, Bart M. P.
  • Jansen, Maurice
  • Kara, Ahmet
  • Kerenidis, Iordanis
  • Khandekar, Rohit
  • Köbler, Johannes
  • Kupferman, Orna
  • Laroussinie, François
  • Lasota, Slawomir
  • Leroux, Jérôme
  • Lodaya, Kamal
  • Lokshtanov, Daniel
  • Maffei, Matteo
  • Mahajan, Meena
  • Markey, Nicolas
  • Matsliah, Arie
  • Misra, Neeldhara
  • Mogavero, Fabio
  • Mohammadi, Esfandiar
  • Mukund, Madhavan
  • Murano, Aniello
  • Muscholl, Anca
  • Narayan Kumar, K.
  • Nicaud, Cyril
  • Obdrzálek, Jan
  • Ordyniak, Sebastian
  • Ouaknine, Joël
  • Pandit, Vinayaka
  • Paulusma, Daniel
  • Philip, Geevarghese
  • Pivoteau, Carine
  • Pudlák, Pavel
  • Qiao, Youming
  • Radcliffe, Nicholas
  • Raman, Venkatesh
  • Raskhodnikova, Sofya
  • Raskin, Jean-François
  • Razet, Benoît
  • Rosamond, Frances A.
  • Roy, Sambuddha
  • Ruan, Ge
  • Rutten, Jan J. M. M.
  • Sabharwal, Yogish
  • Saket, Rishi
  • Sarma M.N., Jayalal
  • Saurabh, Saket
  • Schewe, Sven
  • Schieber, Baruch
  • Schulz, Stefan
  • Schwentick, Thomas
  • Shachnai, Hadas
  • Sikora, Jamie
  • Silva, Alexandra
  • Sistla, A. Prasad
  • Stefankovic, Daniel
  • Steinitz, Avital
  • Szeider, Stefan
  • Tamir, Tami
  • To, Anthony Widjaja
  • Toda, Seinosuke
  • Torán, Jacobo
  • Tripathi, Pushkar
  • Vardi, Moshe Y.
  • Vempala, Santosh S.
  • Verma, Rakesh M.
  • Viswanathan, Mahesh
  • Wagner, Fabian
  • Wang, Lei
  • Worrell, James
  • Wu, Zhilin
  • Yoshida, Nobuko
  • Zeitoun, Marc
  • Zeume, Thomas
  • Zielonka, Wieslaw
    		•

    		  
    Frontmatter, Table of Contents, Preface, Conference Organization, Author Index
    Authors: Lodaya, Kamal ; Mahajan, Meena

    Abstract | Document (345 KB) | BibTeX

    Expressiveness of streaming string transducers
    Authors: Alur, Rajeev ; Černý, Pavol

    Abstract | Document (481 KB) | BibTeX

    Special tree-width and the verification of monadic second-order graph pr operties
    Authors: Courcelle, Bruno

    Abstract | Document (502 KB) | BibTeX

    On extracting computations from propositional proofs (a survey)
    Authors: Pudlák, Pavel

    Abstract | Document (415 KB) | BibTeX

    Recent Progress and Open Problems in Algorithmic Convex Geometry
    Authors: Vempala, Santosh S.

    Abstract | Document (535 KB) | BibTeX

    Playing in stochastic environment: from multi-armed bandits to two-player games
    Authors: Zielonka, Wieslaw

    Abstract | Document (413 KB) | BibTeX

    Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
    Authors: Ganian, Robert ; Hlinený, Petr ; Obdrzálek, Jan

    Abstract | Document (484 KB) | BibTeX

    Satisfiability of Acyclic and Almost Acyclic CNF Formulas
    Authors: Ordyniak, Sebastian ; Paulusma, Daniel ; Szeider, Stefan

    Abstract | Document (468 KB) | BibTeX

    The effect of girth on the kernelization complexity of Connected Dominating Set
    Authors: Misra, Neeldhara ; Philip, Geevarghese ; Raman, Venkatesh ; Saurabh, Saket

    Abstract | Document (549 KB) | BibTeX

    One-Counter Stochastic Games
    Authors: Brázdil, Tomás ; Brozek, Václav ; Etessami, Kousha

    Abstract | Document (545 KB) | BibTeX

    ATL with Strategy Contexts: Expressiveness and Model Checking
    Authors: Da Costa, Arnaud ; Laroussinie, François ; Markey, Nicolas

    Abstract | Document (591 KB) | BibTeX

    Reasoning About Strategies
    Authors: Mogavero, Fabio ; Murano, Aniello ; Vardi, Moshe Y.

    Abstract | Document (241 KB) | BibTeX

    New Results on Quantum Property Testing
    Authors: Chakraborty, Sourav ; Fischer, Eldar ; Matsliah, Arie ; de Wolf, Ronald

    Abstract | Document (522 KB) | BibTeX

    Lower bounds for Quantum Oblivious Transfer
    Authors: Chailloux, André ; Kerenidis, Iordanis ; Sikora, Jamie

    Abstract | Document (503 KB) | BibTeX

    Minimizing Busy Time in Multiple Machine Real-time Scheduling
    Authors: Khandekar, Rohit ; Schieber, Baruch ; Shachnai, Hadas ; Tamir, Tami

    Abstract | Document (552 KB) | BibTeX

    A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints
    Authors: Chakaravarthy, Venkatesan T. ; Choudhury, Anamitra R. ; Sabharwal, Yogish

    Abstract | Document (409 KB) | BibTeX

    Place-Boundedness for Vector Addition Systems with one zero-test
    Authors: Bonnet, Rémi ; Finkel, Alain ; Leroux, Jérôme ; Zeitoun, Marc

    Abstract | Document (504 KB) | BibTeX

    Model checking time-constrained scenario-based specifications
    Authors: Akshay, S. ; Gastin, Paul ; Mukund, Madhavan ; Narayan Kumar, K.

    Abstract | Document (611 KB) | BibTeX

    Global Model Checking of Ordered Multi-Pushdown Systems
    Authors: Atig, Mohamed Faouzi

    Abstract | Document (418 KB) | BibTeX

    The Complexity of Model Checking (Collapsible) Higher-Order Pushdown Systems
    Authors: Hague, Matthew ; To, Anthony Widjaja

    Abstract | Document (459 KB) | BibTeX

    A graph polynomial for independent sets of bipartite graphs
    Authors: Ge, Qi ; Stefankovic, Daniel

    Abstract | Document (483 KB) | BibTeX

    Finding Independent Sets in Unions of Perfect Graphs
    Authors: Chakaravarthy, Venkatesan T. ; Pandit, Vinayaka ; Roy, Sambuddha ; Sabharwal, Yogish

    Abstract | Document (392 KB) | BibTeX

    Fast equivalence-checking for normed context-free processes
    Authors: Czerwinski, Wojciech ; Lasota, Slawomir

    Abstract | Document (540 KB) | BibTeX

    Generalizing the powerset construction, coalgebraically
    Authors: Silva, Alexandra ; Bonchi, Filippo ; Bonsangue, Marcello M. ; Rutten, Jan J. M. M.

    Abstract | Document (501 KB) | BibTeX

    Uniqueness of Normal Forms is Decidable for Shallow Term Rewrite Systems
    Authors: Radcliffe, Nicholas ; Verma, Rakesh M.

    Abstract | Document (458 KB) | BibTeX

    Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
    Authors: Jansen, Maurice ; Qiao, Youming ; Sarma M.N., Jayalal

    Abstract | Document (530 KB) | BibTeX

    Computing Rational Radical Sums in Uniform TC^0
    Authors: Hunter, Paul ; Bouyer, Patricia ; Markey, Nicolas ; Ouaknine, Joël ; Worrell, James

    Abstract | Document (542 KB) | BibTeX

    Graph Isomorphism is not AC^0 reducible to Group Isomorphism
    Authors: Chattopadhyay, Arkadev ; Torán, Jacobo ; Wagner, Fabian

    Abstract | Document (502 KB) | BibTeX

    Colored Hypergraph Isomorphism is Fixed Parameter Tractable
    Authors: Arvind, V. ; Das, Bireswar ; Köbler, Johannes ; Toda, Seinosuke

    Abstract | Document (488 KB) | BibTeX

    Global Escape in Multiparty Sessions
    Authors: Capecchi, Sara ; Giachino, Elena ; Yoshida, Nobuko

    Abstract | Document (248 KB) | BibTeX

    Computationally Sound Abstraction and Verification of Secure Multi-Party Computations
    Authors: Backes, Michael ; Maffei, Matteo ; Mohammadi, Esfandiar

    Abstract | Document (529 KB) | BibTeX

    Model Checking Concurrent Programs with Nondeterminism and Randomization
    Authors: Chadha, Rohit ; Sistla, A. Prasad ; Viswanathan, Mahesh

    Abstract | Document (557 KB) | BibTeX

    Two Size Measures for Timed Languages
    Authors: Asarin, Eugene ; Degorre, Aldric

    Abstract | Document (605 KB) | BibTeX

    Average Analysis of Glushkov Automata under a BST-Like Model
    Authors: Nicaud, Cyril ; Pivoteau, Carine ; Razet, Benoît

    Abstract | Document (742 KB) | BibTeX

    Beyond Hyper-Minimisation---Minimising DBAs and DPAs is NP-Complete
    Authors: Schewe, Sven

    Abstract | Document (421 KB) | BibTeX

    Parityizing Rabin and Streett
    Authors: Boker, Udi ; Kupferman, Orna ; Steinitz, Avital

    Abstract | Document (470 KB) | BibTeX

    Finding Sparser Directed Spanners
    Authors: Berman, Piotr ; Raskhodnikova, Sofya ; Ruan, Ge

    Abstract | Document (683 KB) | BibTeX

    Combinatorial Problems with Discounted Price Functions in Multi-agent Systems
    Authors: Goel, Gagan ; Tripathi, Pushkar ; Wang, Lei

    Abstract | Document (471 KB) | BibTeX

    Quasi-Random PCP and Hardness of 2-Catalog Segmentation
    Authors: Saket, Rishi

    Abstract | Document (456 KB) | BibTeX

    Determining the Winner of a Dodgson Election is Hard
    Authors: Fellows, Michael ; Jansen, Bart M. P. ; Lokshtanov, Daniel ; Rosamond, Frances A. ; Saurabh, Saket

    Abstract | Document (448 KB) | BibTeX

    Verifying Recursive Active Documents with Positive Data Tree Rewriting
    Authors: Genest, Blaise ; Muscholl, Anca ; Wu, Zhilin

    Abstract | Document (515 KB) | BibTeX

    Temporal Logics on Words with Multiple Data Values
    Authors: Kara, Ahmet ; Schwentick, Thomas ; Zeume, Thomas

    Abstract | Document (472 KB) | BibTeX

    First-Order Logic with Reachability Predicates on Infinite Systems
    Authors: Schulz, Stefan

    Abstract | Document (608 KB) | BibTeX

    Generalized Mean-payoff and Energy Games
    Authors: Chatterjee, Krishnendu ; Doyen, Laurent ; Henzinger, Thomas A. ; Raskin, Jean-François

    Abstract | Document (467 KB) | BibTeX

    		  



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