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.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.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.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)
Kamal Lodaya and Meena Mahajan. LIPIcs, Volume 8, FSTTCS'10, Complete Volume. In 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.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)
Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, and Yogish Sabharwal. Finding Independent Sets in Unions of Perfect Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 251-259, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2010.251, author = {Chakaravarthy, Venkatesan T. and Pandit, Vinayaka and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Finding Independent Sets in Unions of Perfect Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {251--259}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.251}, URN = {urn:nbn:de:0030-drops-28683}, doi = {10.4230/LIPIcs.FSTTCS.2010.251}, annote = {Keywords: Approximation Algorithms; Comparability Graphs; Hardness of approximation} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Wojciech Czerwinski and Slawomir Lasota. Fast equivalence-checking for normed context-free processes. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 260-271, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{czerwinski_et_al:LIPIcs.FSTTCS.2010.260, author = {Czerwinski, Wojciech and Lasota, Slawomir}, title = {{Fast equivalence-checking for normed context-free processes}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {260--271}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.260}, URN = {urn:nbn:de:0030-drops-28690}, doi = {10.4230/LIPIcs.FSTTCS.2010.260}, annote = {Keywords: bisimulation, norm, context-free grammar, simple grammar} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. Generalizing the powerset construction, coalgebraically. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 272-283, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{silva_et_al:LIPIcs.FSTTCS.2010.272, author = {Silva, Alexandra and Bonchi, Filippo and Bonsangue, Marcello M. and Rutten, Jan J. M. M.}, title = {{Generalizing the powerset construction, coalgebraically}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {272--283}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.272}, URN = {urn:nbn:de:0030-drops-28706}, doi = {10.4230/LIPIcs.FSTTCS.2010.272}, annote = {Keywords: coalgebra, language equivalence, bisimilarity, powerset construction} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Nicholas Radcliffe and Rakesh M. Verma. Uniqueness of Normal Forms is Decidable for Shallow Term Rewrite Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 284-295, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{radcliffe_et_al:LIPIcs.FSTTCS.2010.284, author = {Radcliffe, Nicholas and Verma, Rakesh M.}, title = {{Uniqueness of Normal Forms is Decidable for Shallow Term Rewrite Systems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {284--295}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.284}, URN = {urn:nbn:de:0030-drops-28715}, doi = {10.4230/LIPIcs.FSTTCS.2010.284}, annote = {Keywords: term rewrite systems, uniqueness of normal forms, decidability, shallo w rewrite systems, flat rewrite systems} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Maurice Jansen, Youming Qiao, and Jayalal Sarma M.N.. Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 296-307, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{jansen_et_al:LIPIcs.FSTTCS.2010.296, author = {Jansen, Maurice and Qiao, Youming and Sarma M.N., Jayalal}, title = {{Deterministic Black-Box Identity Testing \$pi\$-Ordered Algebraic Branching Programs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {296--307}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.296}, URN = {urn:nbn:de:0030-drops-28728}, doi = {10.4230/LIPIcs.FSTTCS.2010.296}, annote = {Keywords: ordered algebraic branching program, polynomial identity testing} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Paul Hunter, Patricia Bouyer, Nicolas Markey, Joël Ouaknine, and James Worrell. Computing Rational Radical Sums in Uniform TC^0. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 308-316, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{hunter_et_al:LIPIcs.FSTTCS.2010.308, author = {Hunter, Paul and Bouyer, Patricia and Markey, Nicolas and Ouaknine, Jo\"{e}l and Worrell, James}, title = {{Computing Rational Radical Sums in Uniform TC^0}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {308--316}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.308}, URN = {urn:nbn:de:0030-drops-28739}, doi = {10.4230/LIPIcs.FSTTCS.2010.308}, annote = {Keywords: Sum of square roots, Threshold circuits, Complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner. Graph Isomorphism is not AC^0 reducible to Group Isomorphism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 317-326, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{chattopadhyay_et_al:LIPIcs.FSTTCS.2010.317, author = {Chattopadhyay, Arkadev and Tor\'{a}n, Jacobo and Wagner, Fabian}, title = {{Graph Isomorphism is not AC^0 reducible to Group Isomorphism}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {317--326}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.317}, URN = {urn:nbn:de:0030-drops-28748}, doi = {10.4230/LIPIcs.FSTTCS.2010.317}, annote = {Keywords: Complexity, Algorithms, Group Isomorphism Problem, Circuit Com plexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
V. Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda. Colored Hypergraph Isomorphism is Fixed Parameter Tractable. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 327-337, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2010.327, author = {Arvind, V. and Das, Bireswar and K\"{o}bler, Johannes and Toda, Seinosuke}, title = {{Colored Hypergraph Isomorphism is Fixed Parameter Tractable}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {327--337}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.327}, URN = {urn:nbn:de:0030-drops-28751}, doi = {10.4230/LIPIcs.FSTTCS.2010.327}, annote = {Keywords: Fixed parameter tractability, fpt algorithms, graph isomorphism, computational complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Sara Capecchi, Elena Giachino, and Nobuko Yoshida. Global Escape in Multiparty Sessions. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 338-351, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{capecchi_et_al:LIPIcs.FSTTCS.2010.338, author = {Capecchi, Sara and Giachino, Elena and Yoshida, Nobuko}, title = {{Global Escape in Multiparty Sessions}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {338--351}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.338}, URN = {urn:nbn:de:0030-drops-28760}, doi = {10.4230/LIPIcs.FSTTCS.2010.338}, annote = {Keywords: escape mechanism, exception handling, multiparty communication} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Michael Backes, Matteo Maffei, and Esfandiar Mohammadi. Computationally Sound Abstraction and Verification of Secure Multi-Party Computations. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 352-363, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{backes_et_al:LIPIcs.FSTTCS.2010.352, author = {Backes, Michael and Maffei, Matteo and Mohammadi, Esfandiar}, title = {{Computationally Sound Abstraction and Verification of Secure Multi-Party Computations}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {352--363}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.352}, URN = {urn:nbn:de:0030-drops-28771}, doi = {10.4230/LIPIcs.FSTTCS.2010.352}, annote = {Keywords: Computational soundness, Secure multi-party computation, Process calculi, Protocol verification} }
Feedback for Dagstuhl Publishing