LIPIcs, Volume 8
FSTTCS 2010, December 15-18, 2010, Chennai, India
Editors: Kamal Lodaya and Meena Mahajan
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
M. Praveen. What You Must Remember When Transforming Datawords. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{praveen:LIPIcs.FSTTCS.2020.55, author = {Praveen, M.}, title = {{What You Must Remember When Transforming Datawords}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {55:1--55:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.55}, URN = {urn:nbn:de:0030-drops-132967}, doi = {10.4230/LIPIcs.FSTTCS.2020.55}, annote = {Keywords: Streaming String Transducers, Data words, Machine independent characterization} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Anantha Padmanabha and R. Ramanujam. Two variable fragment of Term Modal Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{padmanabha_et_al:LIPIcs.MFCS.2019.30, author = {Padmanabha, Anantha and Ramanujam, R.}, title = {{Two variable fragment of Term Modal Logic}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.30}, URN = {urn:nbn:de:0030-drops-109741}, doi = {10.4230/LIPIcs.MFCS.2019.30}, annote = {Keywords: Term modal logic, satisfiability problem, two variable fragment, decidability} }
Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, and Howard Straubing. An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{krebs_et_al:LIPIcs.CSL.2018.28, author = {Krebs, Andreas and Lodaya, Kamal and Pandya, Paritosh K. and Straubing, Howard}, title = {{An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation}}, booktitle = {27th EACSL Annual Conference on Computer Science Logic (CSL 2018)}, pages = {28:1--28:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-088-0}, ISSN = {1868-8969}, year = {2018}, volume = {119}, editor = {Ghica, Dan R. and Jung, Achim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.28}, URN = {urn:nbn:de:0030-drops-96953}, doi = {10.4230/LIPIcs.CSL.2018.28}, annote = {Keywords: two-variable logic, finite model theory, algebraic automata theory} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Proceedings{lodaya_et_al:LIPIcs.FSTTCS.2010, title = {{LIPIcs, Volume 8, FSTTCS'10, Complete Volume}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2013}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010}, URN = {urn:nbn:de:0030-drops-41027}, doi = {10.4230/LIPIcs.FSTTCS.2010}, annote = {Keywords: Software/Program Verification, Models of Computation, Modes of Computation, Complexity Measures and Classes, Nonnumerical Algorithms and Problems pecifying and Verifying and Reasoning about Program} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Rajeev Alur and Pavol Černý. Expressiveness of streaming string transducers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{alur_et_al:LIPIcs.FSTTCS.2010.1, author = {Alur, Rajeev and \v{C}ern\'{y}, Pavol}, title = {{Expressiveness of streaming string transducers}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {1--12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.1}, URN = {urn:nbn:de:0030-drops-28538}, doi = {10.4230/LIPIcs.FSTTCS.2010.1}, annote = {Keywords: streaming string transducer, list processing, heap manipulation, monadic second-order transduction} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Bruno Courcelle. Special tree-width and the verification of monadic second-order graph pr operties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 13-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{courcelle:LIPIcs.FSTTCS.2010.13, author = {Courcelle, Bruno}, title = {{Special tree-width and the verification of monadic second-order graph pr operties}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {13--29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.13}, URN = {urn:nbn:de:0030-drops-28494}, doi = {10.4230/LIPIcs.FSTTCS.2010.13}, annote = {Keywords: model-checking, monadic second-order logic, fixed-parameter tractability, special tree-width} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Pavel Pudlák. On extracting computations from propositional proofs (a survey). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 30-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{pudlak:LIPIcs.FSTTCS.2010.30, author = {Pudl\'{a}k, Pavel}, title = {{On extracting computations from propositional proofs (a survey)}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {30--41}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.30}, URN = {urn:nbn:de:0030-drops-28512}, doi = {10.4230/LIPIcs.FSTTCS.2010.30}, annote = {Keywords: proof complexity, propositional tautology, boolean circuits, resolution, feasible interpolation} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Santosh S. Vempala. Recent Progress and Open Problems in Algorithmic Convex Geometry. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 42-64, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{vempala:LIPIcs.FSTTCS.2010.42, author = {Vempala, Santosh S.}, title = {{Recent Progress and Open Problems in Algorithmic Convex Geometry}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {42--64}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.42}, URN = {urn:nbn:de:0030-drops-28529}, doi = {10.4230/LIPIcs.FSTTCS.2010.42}, annote = {Keywords: convex geometry, geometric inequalities, algorithms, sampling, optimization, integration, rounding, learning} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Wieslaw Zielonka. Playing in stochastic environment: from multi-armed bandits to two-player games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 65-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{zielonka:LIPIcs.FSTTCS.2010.65, author = {Zielonka, Wieslaw}, title = {{Playing in stochastic environment: from multi-armed bandits to two-player games}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {65--72}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.65}, URN = {urn:nbn:de:0030-drops-28500}, doi = {10.4230/LIPIcs.FSTTCS.2010.65}, annote = {Keywords: two-player zero-sum game, one-player zero-sum game, multi-armed bandit, memoryless deterministic strategy} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Robert Ganian, Petr Hlinený, and Jan Obdrzálek. Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 73-83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{ganian_et_al:LIPIcs.FSTTCS.2010.73, author = {Ganian, Robert and Hlinen\'{y}, Petr and Obdrz\'{a}lek, Jan}, title = {{Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {73--83}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.73}, URN = {urn:nbn:de:0030-drops-28541}, doi = {10.4230/LIPIcs.FSTTCS.2010.73}, annote = {Keywords: propositional model counting; satisfiability; rank-width; clique-width ; parameterized complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 84-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{ordyniak_et_al:LIPIcs.FSTTCS.2010.84, author = {Ordyniak, Sebastian and Paulusma, Daniel and Szeider, Stefan}, title = {{Satisfiability of Acyclic and Almost Acyclic CNF Formulas}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {84--95}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.84}, URN = {urn:nbn:de:0030-drops-28556}, doi = {10.4230/LIPIcs.FSTTCS.2010.84}, annote = {Keywords: Satisfiability, chordal bipartite graphs, beta-acyclic hypergraphs, backdoor sets, parameterized complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. The effect of girth on the kernelization complexity of Connected Dominating Set. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 96-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{misra_et_al:LIPIcs.FSTTCS.2010.96, author = {Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket}, title = {{The effect of girth on the kernelization complexity of Connected Dominating Set}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {96--107}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.96}, URN = {urn:nbn:de:0030-drops-28567}, doi = {10.4230/LIPIcs.FSTTCS.2010.96}, annote = {Keywords: Connected Dominating Set, parameterized complexity, kernelization, girth} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Tomás Brázdil, Václav Brozek, and Kousha Etessami. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 108-119, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2010.108, author = {Br\'{a}zdil, Tom\'{a}s and Brozek, V\'{a}clav and Etessami, Kousha}, title = {{One-Counter Stochastic Games}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {108--119}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.108}, URN = {urn:nbn:de:0030-drops-28571}, doi = {10.4230/LIPIcs.FSTTCS.2010.108}, annote = {Keywords: one-counter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Arnaud Da Costa, François Laroussinie, and Nicolas Markey. ATL with Strategy Contexts: Expressiveness and Model Checking. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 120-132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{dacosta_et_al:LIPIcs.FSTTCS.2010.120, author = {Da Costa, Arnaud and Laroussinie, Fran\c{c}ois and Markey, Nicolas}, title = {{ATL with Strategy Contexts: Expressiveness and Model Checking}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {120--132}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.120}, URN = {urn:nbn:de:0030-drops-28589}, doi = {10.4230/LIPIcs.FSTTCS.2010.120}, annote = {Keywords: alternating temporal logic, agent, strategy quantifier} }
Feedback for Dagstuhl Publishing