Fundamentals of Computing and Discrete Mathematics

Publications

Articles and conference papers published during the FiDiPro project.

Recent Preprints

  • “Infinite self-shuffling words”, (E. Charlier, T. Kamae, S. Puzynina, L.Q. Zamboni), preprint 2013 arXiv.
  • “On a question of Hof, Knill and Simon on palindromic substitutive systems”, (T. Harju, J. Vesti, L.Q. Zamboni), preprint 2013, arXiv.
  • “On generating binary words palindromically”, (T. Harju, M. Huova, L.Q. Zamboni), preprint 2013, arXiv.
  • “Existence of an infinite ternary 64-abelian square-free word”, (M. Huova), (submitted)
  • “Variations of the Morse-Hedlund Theorem for k-abelian equivalence”, (J. Karhumäki, A. Saarela, L.Q. Zamboni), (2013), arXiv.
  • “Privileged factors in the Thue-Morse word - A comparison of privileged words and palindromes”, (J. Peltomäki), (2013), arXiv.

2014: Journal Papers, Conference Papers

Journal Papers

  • “A coloring problem for infinite words”, (A. de Luca, E. Pribavkina, L.Q. Zamboni), J. Combin. Theory Ser. A, 125C (2014), 306–332 arXiv.
  • “Additive properties of sets and substitutive dynamics”, (S. Puzynina, L.Q. Zamboni), to appear in "Directions in Aperiodic Order" Progress in Mathematics, Birkhauser Publishing (2014).
  • “Extremal words in morphic subshifts”, (J.D. Currie, N. Rampersad, K. Saari, L.Q. Zamboni), Discrete Math. 322 (2014), 53–60 arXiv.
  • “Lyndon words and Fibonacci numbers”, (K. Saari), J. Combin. Theory Ser. A 121 (2014), 34–44, arXiv.

2013: Journal Papers, Conference Papers

Journal Papers

  • “Fine and Wilf's theorem for k-abelian periods”, (J. Karhumäki, S.Puzynina, A. Saarela), to appear in Int. J. Found. Comput. Sci. (2013).
  • “On a generalization of Abelian equivalence and complexity of infinite words”, (J. Karhumäki, A. Saarela, L.Q. Zamboni), J. Combin. Theory Ser. A 120 (2013), no. 8, 2189–2206 arXiv.
  • “Central sets and substitutive dynamical systems”, (M. Barge, L.Q. Zamboni), Adv. Math. 248 (2013), 308–323 arXiv.
  • “Abelian maximal pattern complexity of words”, (T. Kamae, S. Widmer, L.Q. Zamboni), (2013), Ergodic Theory & Dynam. Systems (First published online 2013), doi:10.1017/etds.2013.51, 1235–1245 arXiv.
  • “Central sets generated by uniformly recurrent words”, (M. Bucci, S. Puzynina, L.Q. Zamboni), Ergodic Theory & Dynam. Systems (2013), in press arXiv.
  • “On additive properties of sets defined by the Thue-Morse word”, (M. Bucci, N. Hindman, S. Puzynina, L.Q. Zamboni), J. Combin. Theory Ser. A 120 (2013), no. 6, 1235–1245 arXiv .
  • “Reversible Christoffel factorizations”, (M. Bucci, A. De Luca, L.Q. Zamboni), Theoret. Comput. Sci. 495 (2013), 17–24 arXiv.
  • “On the least number of palindromes contained in an infinite word”, (G. Fici, L.Q. Zamboni), Theoret. Comput. Sci. 481 (2013), 1–8 arXiv.
  • “Introducing privileged words: privileged complexity of Sturmian words”, (J. Peltomäki), Theoret. Comput. Sci. 500 (2013), 57–67 arXiv.
  • “Clustering words”, (S. Ferenczi, L.Q. Zamboni), J. Integer Seq. 16 (2013), no. 2, Article 13.2.1 arXiv.
  • “On palindromic factorization of words”, (A. Frid, S. Puzynina, L.Q. Zamboni), Adv. in Appl. Math. 50 (2013), no. 5, 737–748 doi.
  • “A regularity lemma and twins in words”, (M. Axenovich, Y. Person, S. Puzynina), J. Combin. Theory Ser. A 120 (2013), no. 4, 733–743.
  • “Abelian returns in Sturmian words”, (S. Puzynina, L.Q. Zamboni), J. Combin. Theory Ser. A 120 (2013), no. 2, 390–408.
  • “On the Unavoidability of k-Abelian Squares in Pure Morphic Words”, (M. Huova, J. Karhumäki), J. Integer Seq. (2013), in press
  • “Enumeration and Structure of Trapezoidal Words, (M. Bucci, A. De Luca, G. Fici), Theoret. Comput. Sci. 468 (2013), 12–22

Conference Papers

  • “3-abelian cubes are avoidable on binary alphabets”, (R. Mercas, A. Saarela), Lecture Notes in Computer Science 7907 DLT 2013: 374–383.
  • “Infinite words with well distributed occurrences”, (L. Balková, M. Bucci, A. De Luca, S. Puzynina ), Lecture Notes in Computer Science 8079 WORDS 2013: 46–57.
  • “Strongly k-abelian repetitions”, (M. Huova, A. Saarela), Lecture Notes in Computer Science 8079 WORDS 2013: 161–168.
  • “Weakly unambiguous morphisms with respect to sets of patterns with constants”, (A. Saarela), Lecture Notes in Computer Science 8079 WORDS 2013: 229–237.
  • “A coloring problem for Sturmian and episturmian words”, (A. de Luca, E. Pribavkina, L.Q. Zamboni), Lecture Notes in Computer Science 7907 DLT 2013: 191–202 arXiv.
  • “Self-shuffling Words”, (E. Charlier, T. Kamae, S. Puzynina, L.Q. Zamboni), Lecture Notes in Computer Science 7966 ICALP (2) 2013: 113–124 arXiv.

2012: Journal Papers, Conference Papers

Journal Papers

  • “Some characterizations of Sturmian Words in terms of the lexicographic order”, (M. Bucci, A. De Luca, L.Q. Zamboni), Fund. Inform. 116 (2012), 25–33.
  • “On automatic infinite permutations”, (A. Frid, L.Q. Zamboni), Theor. Inform. Appl. (RAIRO) 46 (2012), 77–85.
  • “Problems in between words and abelian words: k-abelian avoidability”, (M.Huova, J. Karhumäki, A. Saarela), Theoret. Comput. Sci. 454 (2012), 172–177.
  • “On abelian versions of Critical Factorization Theorem”, (S. Avgustinovich, J. Karhumäki, S. Puzynina), Theor. Inform. Appl. (RAIRO) 46 (2012), 3–15
  • “Square-free words obtained from prefixes by permutations”, (T. Harju), Theoret. Comput. Sci. 429 (2012), 128–133.

Conference Papers

  • “On k-abelian avoidability”, (M. Huova, J. Karhumäki), in J. Karhumäki and Y. Matiyasevich (eds.): Combinatorics and graph theory Part IV, RuFiDiM 2011, Zap. Nauchn. Sem. POMI, 402 (2012) 170–182
  • “5-abelian cubes are avoidable on binary alphabets”, (R. Mercas, A. Saarela), Internal Proceedings of the 14th Mons Days of Theoretical Computer Science (2012)
  • “Palindromic defect of pure morphic words”, (M. Bucci, E. Vaslet), Internal Proceedings of the 14th Mons Days of Theoretical Computer Science (2012)
  • “On Minimal Factorizations of Words as Products of Palindromes”, (A. Frid, S. Puzynina, L.Q. Zamboni), Internal Proceedings of the 14th Mons Days of Theoretical Computer Science (2012)
  • “Additive properties of sets of factors of the Thue-Morse word”, (M. Bucci, N. Hindman, S. Puzynina, L.Q. Zamboni), Internal Proceedings of the 14th Mons Days of Theoretical Computer Science (2012)
  • “Fine and Wilf's theorem for k-abelian periods”, (J. Karhumäki, S.Puzynina, A. Saarela), Proceedings of the 16th International Conference on Developments in Language Theory (2012) 296-307

2011: Journal Papers, Conference Papers

Journal Papers

  • “Eigenvalues and simplicity of interval exchange transformations”, (S. Ferenczi, L.Q. Zamboni), Ann. Sci. Éc. Norm. Supér. (4) 44 (2011), 361–392.
  • “Abelian complexity of minimal subshifts”, (G. Richomme, K. Saari, L.Q. Zamboni), J. Lond. Math. Soc. (2) 83 (2011), 79–95.
  • “Unique decipherability in the monoid of languages: an application of rational relations”, (C. Choffrut, J. Karhumäki), Theory Comput. Syst. 49 (2011), 355–364
  • “The unique decipherability in the monoid of regular languages is undecidable”, (J. Karhumäki, A. Saarela), Fund. Inform. 110 (2011), 197–200
  • “The number of positions starting a square in binary words”, (T. Harju, T. Kärki, D. Nowotka), Electronic J. Combin. 18 (2011), no. 1, paper 6
  • “On the number of frames in binary words”, (T. Harju, Tomi Kärki), Theoret. Comput. Sci. 412 (2011), 5276–5284.
  • “Combinatorial trees arising in the study of interval exchange transformations”, (J. Cassaigne, S. Ferenczi, L.Q. Zamboni), European J. Combin. 32 (2011), 1428–1444.
  • “Avoiding Abelian powers in binary words with bounded Abelian complexity”, (J. Cassaigne, G. Richomme, K. Saari, L.Q. Zamboni), Internat. J. Found. Comput. Sci. 22 (2011), 905–920 .
  • “Turtle graphics and locally catenative sequences”, (J. Karhumäki, S. Puzynina), Theor. Inform. Appl. (RAIRO) 45 (2011), 311–330.

Conference Papers

  • “Equations in the Partial Semigroup of Words with Overlapping Products”, (M. Huova, J. Karhumäki), Languages Alive 2012, 99–110
  • “Weighted finite automata: computing with different topologies”, (J. Karhumäki, T. Sallinen), Proceedings of Unconventional Computation, LNCS 6714 (2011), 14–33
  • “Local squaresm periodicity and finite automata”, (M. Huova, J. Karhumäki, A. Saarela), Rainbow Computer Science, LNCS 6570 (2011), 90–101
  • “Observations and Problems on k-abelian Avoidability”, (M. Huova, J. Kahumäki), in M. Crochemore, L. Kari, M. Mohri and D. Nowotka (eds.): Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081), Dagstuhl Publishing, 2011, 2215–2219.
  • “Reversible Christoffel factorizations”, (M. Bucci, A. De Luca, L. Zamboni), First Russian-Finnish Symposium on Discrete Mathematics, St. Petersburg, Russia (RuFiDiM 2011) 13–15
  • “Abelian returns in Sturmian words”, (S. Puzynina, L. Zamboni), EPTCS 63, Proceedings of WORDS 2011, 179–188
Last modified: Friday October 10, 2014