Portal - FSTTCS 2014

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

Ayala-Rincón, Mauricio

Chakaravarthy, Venkatesan T.

Chakraborty, Diptarka

de Moura, Flávio L. C.

de Rugy-Altherre, Nicolas

Georgiou, Konstantinos

Giannopoulou, Archontia C.

Krishna, Shankara Narayanan

Papadimitriou, Christos H.

Raskin, Jean-Francois

Rezine, Othmane

Ruiz-Vargas, Andres Jacinto

Venugopalan, Rajeswari

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

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