Gitlab repository

Formalization of Combinatorics on Words in Isabelle/HOL

[Hol17a]

Štěpán Holub. Commutation and beyond. In Srečko Brlek, Francesco Dolce, Christophe Reutenauer, and Élise Vandomme, editors, Combinatorics on Words, pages 1-5, Cham, 2017. Springer International Publishing.
[ bib | DOI |

[HM17]

Štěpán Holub and Mike Müller. Fully bordered words. Theoretical Computer Science, 684:53-58, 2017.
[ bib | DOI | arXiv ]

[Hol17b]

Štěpán Holub. Prefix frequency of lost positions. Theoretical Computer Science, 684:43-52, 2017.
[ bib | DOI | arXiv ]

[HV17]

Štěpán Holub and Robert Veroff. Formalizing a fragment of combinatorics on words. In Jarkko Kari, Florin Manea, and Ion Petre, editors, Unveiling Dynamics and Complexity, pages 24-31, Cham, 2017. Springer International Publishing.
[ bib | DOI ]

[CH16]

Christian Choffrut and Štěpán Holub. A presentation of a finitely generated submonoid of invertible endomorphisms of the free monoid. Semigroup Forum, 93(3):444-458, 2016.
[ bib | DOI | Preprint ]

[HS16]

Štepán Holub and Jeffrey Shallit. Periods and Borders of Random Words. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1-44:10, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[ bib | DOI ]

[HH15]

Jana Hadravová and Štěpán Holub. Equation xⁱy^jx^k=uⁱv^ju^k in words. In Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications, volume 8977 of Lecture Notes in Computer Science, pages 414-423. Springer International Publishing, 2015.
[ bib | DOI | arXiv ]

[HŽ15]

Štěpán Holub and Jan Žemlička. Algebraic properties of word equations. Journal of Algebra, 434(0):283 - 301, 2015.
[ bib | DOI | arXiv ]

[FHIL15]

Johannes Fischer, Štěpán Holub, Tomohiro I, and Moshe Lewenstein. Beyond the runs theorem. In Costas Iliopoulos, Simon Puglisi, and Emine Yilmaz, editors, String Processing and Information Retrieval, volume 9309 of Lecture Notes in Computer Science, pages 277-286. Springer International Publishing, 2015.
[ bib | DOI | arXiv ]

[Hol14]

Štěpán Holub. Words with unbounded periodicity complexity. International Journal of Algebra and Computation, 24(6):827-836, 2014.
[ bib | DOI | arXiv ]

[CFH⁺14]

Arturo Carpi, Gabriele Fici, Štěpán Holub, Jakub Opršal, and Marinella Sciortino. Universal lyndon words. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014, volume 8634 of Lecture Notes in Computer Science, pages 135-146. Springer Berlin Heidelberg, 2014.
[ bib | DOI | arXiv ]

[HJM14]

Štěpán Holub, Galina Jirásková, and Tomáš Masopust. On upper and lower bounds on the length of alternating towers. In Mathematical Foundations of Computer Science 2014, pages 315-326. Springer Berlin Heidelberg, 2014.
[ bib | DOI | arXiv ]

[HM13]

Štěpán Holub and Vojtěch Matocha. Complexity of testing morphic primitivity. Kybernetika, 49(2):216-223, 2013.
[ bib | Preprint | arXiv ]

[Hol13a]

Štěpán Holub. Abelian powers in paper-folding words. Journal of Combinatorial Theory, Series A, 120(4):872 - 881, 2013.
[ bib | DOI | arXiv ]

[Hol13b]

Štěpán Holub. On an algorithm for multiperiodic words. Acta Polytechnica, 53(4):344-346, 2013.
[ bib | arXiv | http ]

[HH12]

Jana Hadravová and Štěpán Holub. Large simple binary equality words. Internat. J. Found. Comput. Sci., 23(6):1385-1403, 2012.
[ bib | DOI | Conference version | Preprint | http ]

[HN12]

Štěpán Holub and Dirk Nowotka. The Ehrenfeucht-Silberger problem. J. Comb. Theory, Ser. A, 119(3):668 - 682, 2012.
[ bib | DOI | Conference version | Preprint ]

[Hol11b]

Štěpán Holub. Corrigendum: On multiperiodic words. Theor. Inform. Appl., 45(4):467-469, 2011.
[ bib | DOI ]

[HK11]

Štěpán Holub and Juha Kortelainen. On partitions separating two words. International Journal of Algebra and Computation, 21(8):1305-1316, 2011.
[ bib | DOI | Preprint ]

[HH11]

Vesa Halava and Štěpán Holub. Reduction tree of the binary generalized Post Correspondence Problem. Internat. J. Found. Comput. Sci., 22(2):473-490, 2011.
[ bib | DOI | Preprint ]

[Hol11a]

Štěpán Holub. Binary morphisms with stable suffix complexity. Internat. J. Found. Comput. Sci., 22(3):699-712, 2011.
[ bib | DOI | Preprint ]

[HN10]

Štěpán Holub and Dirk Nowotka. On the relation between periodicity and unbordered factors of finite words. Internat. J. Found. Comput. Sci., 21(4):633-645, 2010.
[ bib | DOI | Preprint ]

[HS09]

Štěpán Holub and Kalle Saari. On highly palindromic words. Discrete Appl. Math., 157(5):953-959, 2009.
[ bib | DOI | Preprint ]

[Hol09]

Štěpán Holub. Polynomial-time algorithm for fixed points of nontrivial morphisms. Discrete Math., 309(16):5069-5076, 2009.
[ bib | DOI | Preprint ]

[HN09]

Štěpán Holub and Dirk Nowotka. The Ehrenfeucht-Silberger problem. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, volume 5555 of Lecture Notes in Computer Science, pages 537-548. Springer Berlin Heidelberg, 2009.
[ bib | DOI ]

[Hol08]

Štěpán Holub. Parikh test sets for commutative languages. Theor. Inform. Appl., 42(3):525-537, 2008.
[ bib | DOI | Preprint ]

[HH08]

Jana Hadravová and Štěpán Holub. Large simple binary equality words. In Developments in language theory, volume 5257 of Lecture Notes in Comput. Sci., pages 396-407. Springer, Berlin, 2008.
[ bib | DOI ]

[HK07]

Štěpán Holub and Juha Kortelainen. On systems of word equations with simple loop sets. Theoret. Comput. Sci., 380(3):363-372, 2007.
[ bib | DOI ]

[CHKL07]

Elena Czeizler, Štěpán Holub, Juhani Karhumäki, and Markku Laine. Intricacies of simple word equations: an example. Internat. J. Found. Comput. Sci., 18(6):1167-1175, 2007.
[ bib | DOI ]

[Hol06]

Štěpán Holub. On multiperiodic words. Theor. Inform. Appl., 40(4):583-591, 2006.
[ bib | DOI | Erratum | Preprint ]

[HH06]

Vesa Halava and Štěpán Holub. Binary (Generalized) Post Correspondence Problem is in P. Technical Report 785, Turku Centre for Computer Science, Sep 2006.
[ bib | http ]

[Hol05]

Štěpán Holub. A proof of the extended Duval's conjecture. Theoret. Comput. Sci., 339(1):61-67, 2005.
[ bib | DOI | Preprint ]

[Hol04]

Štěpán Holub. Binary equality languages for periodic morphisms. In Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, volume 1366 of RIMS Kokyuroku. Kyoto University, 4 2004.
[ bib | Revised version | http ]

[Hol03b]

Štěpán Holub. A unique structure of two-generated binary equality sets. In Developments in language theory, volume 2450 of Lecture Notes in Comput. Sci., pages 245-257. Springer, Berlin, 2003.
[ bib | DOI | Preprint ]

[Hol03a]

Štěpán Holub. Binary equality sets are generated by two words. J. Algebra, 259(1):1-42, 2003.
[ bib | DOI | Revised version ]

[Hol01]

Štěpán Holub. Local and global cyclicity in free semigroups. Theoret. Comput. Sci., 262(1-2):25-36, 2001.
[ bib | DOI | Preprint ]

[HK01]

Štěpán Holub and Juha Kortelainen. Linear size test sets for certain commutative languages. Theor. Inform. Appl., 35(5):453-475, 2001.
[ bib | DOI | Preprint ]

[Hol00]

Štěpán Holub. In search of a word with special combinatorial properties. In Computational and geometric aspects of modern algebra (Edinburgh, 1998), volume 275 of London Math. Soc. Lecture Note Ser., pages 120-127. Cambridge Univ. Press, Cambridge, 2000.
[ bib | DOI | Preprint ]

[Hol99]

Štěpán Holub. A solution of the equation (x₁²...x_n²)³=(x₁³... x_n³)². In Contributions to general algebra, 11 (Olomouc/Velké Karlovice, 1998), pages 105-111. Heyn, Klagenfurt, 1999.
[ bib | Preprint ]