LIPIcs, Volume 24
FSTTCS 2013, December 12-14, 2013, Guwahati, India
Editors: Anil Seth and Nisheeth K. Vishnoi
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@Proceedings{seth_et_al:LIPIcs.FSTTCS.2013, title = {{LIPIcs, Volume 24, FSTTCS'13, Complete Volume}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2014}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013}, URN = {urn:nbn:de:0030-drops-44358}, doi = {10.4230/LIPIcs.FSTTCS.2013}, annote = {Keywords: Software/Program Verification, Models of Computation, Modes of Computation, Complexity Measures and Classes, Nonnumerical Algorithms and Problems, Spe Programs, Mathematical Logic, Formal Languages} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{seth_et_al:LIPIcs.FSTTCS.2013.i, author = {Seth, Anil and Vishnoi, Nisheeth K.}, title = {{Frontmatter, Table of Contents, Preface, Conference Organization}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {i--xiv}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.i}, URN = {urn:nbn:de:0030-drops-44041}, doi = {10.4230/LIPIcs.FSTTCS.2013.i}, annote = {Keywords: Frontmatter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Venkatesan Guruswami. Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{guruswami:LIPIcs.FSTTCS.2013.1, author = {Guruswami, Venkatesan}, title = {{Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {1--1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.1}, URN = {urn:nbn:de:0030-drops-43992}, doi = {10.4230/LIPIcs.FSTTCS.2013.1}, annote = {Keywords: Error-correction algorithms, Linear Codes, Shannon capacity, Martingale convergence, Computational complexity} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Martin Hofmann and Ramyaa Ramyaa. Computing With a Fixed Number of Pointers (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 3-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{hofmann_et_al:LIPIcs.FSTTCS.2013.3, author = {Hofmann, Martin and Ramyaa, Ramyaa}, title = {{Computing With a Fixed Number of Pointers}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {3--18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.3}, URN = {urn:nbn:de:0030-drops-44009}, doi = {10.4230/LIPIcs.FSTTCS.2013.3}, annote = {Keywords: Logarithmic space, Jumping graph automata, st-connectivity, co-st-connectivity, Cayley graphs} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Subhash Khot. On Approximation Resistance of Predicates (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, p. 19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{khot:LIPIcs.FSTTCS.2013.19, author = {Khot, Subhash}, title = {{On Approximation Resistance of Predicates}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {19--19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.19}, URN = {urn:nbn:de:0030-drops-44011}, doi = {10.4230/LIPIcs.FSTTCS.2013.19}, annote = {Keywords: Approximation resistance, Hardness of approximation, Probabilistically checkable proofs, Constraint satisfaction problem} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Characterisations of Nowhere Dense Graphs (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 21-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{grohe_et_al:LIPIcs.FSTTCS.2013.21, author = {Grohe, Martin and Kreutzer, Stephan and Siebertz, Sebastian}, title = {{Characterisations of Nowhere Dense Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {21--40}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.21}, URN = {urn:nbn:de:0030-drops-44029}, doi = {10.4230/LIPIcs.FSTTCS.2013.21}, annote = {Keywords: Graph Algorithms, Algorithmic Graph Structure Theory, Finite Model Theory, Nowhere Dense Classes of Graphs} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Kazushige Terui. Intersection Types for Normalization and Verification (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 41-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{terui:LIPIcs.FSTTCS.2013.41, author = {Terui, Kazushige}, title = {{Intersection Types for Normalization and Verification}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {41--42}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.41}, URN = {urn:nbn:de:0030-drops-44032}, doi = {10.4230/LIPIcs.FSTTCS.2013.41}, annote = {Keywords: simply typed lambda calculus, computational complexity, denotational semantics, intersection types} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2013.43, author = {Crowston, Robert and Jones, Mark and Muciaccia, Gabriele and Philip, Geevarghese and Rai, Ashutosh and Saurabh, Saket}, title = {{Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {43--54}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.43}, URN = {urn:nbn:de:0030-drops-43599}, doi = {10.4230/LIPIcs.FSTTCS.2013.43}, annote = {Keywords: Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Henning Fernau, Markus L. Schmid, and Yngve Villanger. On the Parameterised Complexity of String Morphism Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 55-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{fernau_et_al:LIPIcs.FSTTCS.2013.55, author = {Fernau, Henning and Schmid, Markus L. and Villanger, Yngve}, title = {{On the Parameterised Complexity of String Morphism Problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {55--66}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.55}, URN = {urn:nbn:de:0030-drops-43619}, doi = {10.4230/LIPIcs.FSTTCS.2013.55}, annote = {Keywords: String Problems, String Morphisms, Parameterised Complexity, Exponential Time Hypothesis, Pattern Languages} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially Polynomial Kernels for Set Cover and Test Cover. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 67-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{basavaraju_et_al:LIPIcs.FSTTCS.2013.67, author = {Basavaraju, Manu and Francis, Mathew C. and Ramanujan, M. S. and Saurabh, Saket}, title = {{Partially Polynomial Kernels for Set Cover and Test Cover}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {67--78}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.67}, URN = {urn:nbn:de:0030-drops-43621}, doi = {10.4230/LIPIcs.FSTTCS.2013.67}, annote = {Keywords: Set Cover, Test Cover, Kernelization, Parameterized Algorithms} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 79-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{chitnis_et_al:LIPIcs.FSTTCS.2013.79, author = {Chitnis, Rajesh and Fomin, Fedor V. and Golovach, Petr A.}, title = {{Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {79--90}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.79}, URN = {urn:nbn:de:0030-drops-43636}, doi = {10.4230/LIPIcs.FSTTCS.2013.79}, annote = {Keywords: Parameterized complexity, directed graphs, anchored \$k\$-core} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Pierre Clairambault and Andrzej S. Murawski. Böhm Trees as Higher-Order Recursive Schemes. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 91-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{clairambault_et_al:LIPIcs.FSTTCS.2013.91, author = {Clairambault, Pierre and Murawski, Andrzej S.}, title = {{B\"{o}hm Trees as Higher-Order Recursive Schemes}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {91--102}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.91}, URN = {urn:nbn:de:0030-drops-43644}, doi = {10.4230/LIPIcs.FSTTCS.2013.91}, annote = {Keywords: Lambda calculus, B\"{o}hm trees, Recursion Schemes} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Sylvain Salvati and Igor Walukiewicz. Evaluation is MSOL-compatible. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 103-114, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{salvati_et_al:LIPIcs.FSTTCS.2013.103, author = {Salvati, Sylvain and Walukiewicz, Igor}, title = {{Evaluation is MSOL-compatible}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {103--114}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.103}, URN = {urn:nbn:de:0030-drops-43652}, doi = {10.4230/LIPIcs.FSTTCS.2013.103}, annote = {Keywords: Simply typed \$lambda Y\$-calculus; Monadic second order} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Axel Haddad. Model Checking and Functional Program Transformations. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 115-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{haddad:LIPIcs.FSTTCS.2013.115, author = {Haddad, Axel}, title = {{Model Checking and Functional Program Transformations}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {115--126}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.115}, URN = {urn:nbn:de:0030-drops-43605}, doi = {10.4230/LIPIcs.FSTTCS.2013.115}, annote = {Keywords: Higher-order recursion schemes, Model checking, Tree automata} }
Feedback for Dagstuhl Publishing