Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Julien Destombes and Andrei Romashchenko. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{destombes_et_al:LIPIcs.STACS.2019.23, author = {Destombes, Julien and Romashchenko, Andrei}, title = {{Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {23:1--23:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.23}, URN = {urn:nbn:de:0030-drops-102624}, doi = {10.4230/LIPIcs.STACS.2019.23}, annote = {Keywords: Sofic shifts, Block complexity, Kolmogorov complexity} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Bruno Durand and Andrei Romashchenko. On the Expressive Power of Quasiperiodic SFT. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{durand_et_al:LIPIcs.MFCS.2017.5, author = {Durand, Bruno and Romashchenko, Andrei}, title = {{On the Expressive Power of Quasiperiodic SFT}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {5:1--5:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.5}, URN = {urn:nbn:de:0030-drops-80985}, doi = {10.4230/LIPIcs.MFCS.2017.5}, annote = {Keywords: minimal SFT, tilings, quasiperiodicityIn this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations} }
Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)
Alexander Leitsch, Giselle Reis, and Bruno Woltzenlogel Paleo. Towards CERes in intuitionistic logic. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 485-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{leitsch_et_al:LIPIcs.CSL.2012.485, author = {Leitsch, Alexander and Reis, Giselle and Woltzenlogel Paleo, Bruno}, title = {{Towards CERes in intuitionistic logic}}, booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL}, pages = {485--499}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-42-2}, ISSN = {1868-8969}, year = {2012}, volume = {16}, editor = {C\'{e}gielski, Patrick and Durand, Arnaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.485}, URN = {urn:nbn:de:0030-drops-36922}, doi = {10.4230/LIPIcs.CSL.2012.485}, annote = {Keywords: cut-elimination, resolution, LJ} }
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 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Alexis Ballier, Bruno Durand, and Emmanuel Jeandal. Structural aspects of tilings. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 61-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{ballier_et_al:LIPIcs.STACS.2008.1334, author = {Ballier, Alexis and Durand, Bruno and Jeandal, Emmanuel}, title = {{Structural aspects of tilings}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {61--72}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1334}, URN = {urn:nbn:de:0030-drops-13343}, doi = {10.4230/LIPIcs.STACS.2008.1334}, annote = {Keywords: Tiling, domino, patterns, tiling preorder, tiling structure} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi. Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181). Dagstuhl Seminar Report 377, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)
@TechReport{durand_et_al:DagSemRep.377, author = {Durand, Bruno and Levin, Leonid A. and Merkle, Wolfgang and Shen, Alexander and Vitanyi, Paul M. B.}, title = {{Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)}}, pages = {1--6}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {377}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.377}, URN = {urn:nbn:de:0030-drops-152578}, doi = {10.4230/DagSemRep.377}, }
Feedback for Dagstuhl Publishing