Aleksi Saarela

Information

I am a researcher of mathematics in the University of Turku. My email address is of the form firstname.lastname@utu.fi. There is a resume (pdf).


Research

My research area is discrete mathematics, or more precisely combinatorics on words. I have a Google Scholar Citations page.


Publications

2023

(A.40) Saarela:
On the Solution Sets of Entire Systems of Word Equations.
Proceedings of the 14th WORDS, LNCS 13899:261-273, Springer (2023) (doi) (pdf)

2022

(A.39) Nowotka, Saarela:
An optimal bound on the solution sets of one-variable word equations and its consequences.
SIAM J. Comput., 51(1):1-18 (2022) (doi) (pdf)

2021

(D.04) Hakanen, Halava, Herva, Kari, Laihonen, Petre, Saarela:
Proceedings of the Sixth Russian-Finnish Symposium on Discrete Mathematics.
TUCS Lecture Notes 31 (2021) (link)

(A.38) Saarela:
Separating the words of a language by counting factors.
Fund. Inform., 180(4):375-393 (2021) (doi) (pdf)

(A.37) Peltomäki, Saarela:
Standard words and solutions of the word equation X_1^2\cdots X_n^2=(X_1\cdots X_n)^2.
J. Combin. Theory Ser. A 178 (2021) (doi) (arXiv)

2020

(A.36) Saarela:
Hardness results for constant-free pattern languages and word equations.
Proceedings of the 47th ICALP, LIPIcs 168:140:1-140:15, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik (2020) (doi)

(D.03) Saarela:
Combinatorics on Words.
Lecture notes (2020) (pdf)

2019

(A.35) Avgustinovich, Cassaigne, Karhumäki, Puzynina, Saarela:
On abelian saturated infinite words.
Theoret. Comput. Sci., 792(5):154-160 (2019) (doi) (pdf)

(B.05) Saarela:
Independent systems of word equations: From Ehrenfeucht to eighteen.
Proceedings of the 12th WORDS, LNCS 11682:60-67, Springer (2019) (doi)

(A.34) Saarela:
Separating many words by counting occurrences of factors.
Proceedings of the 23rd DLT, LNCS 11647:251-264, Springer (2019) (doi) (arXiv) (Journal version in A.38)

(A.33) Saarela:
Word equations with kth powers of variables.
J. Combin. Theory Ser. A, 165:15-31 (2019) (doi) (pdf)

2018

(A.32) Nowotka, Saarela:
One-variable word equations and three-variable constant-free word equations.
Internat. J. Found. Comput. Sci., 29(5):935-950 (2018) (doi) (pdf)

(A.31) Endrullis, Karhumäki, Klop, Saarela:
Degrees of infinite words, polynomials and atoms.
Internat. J. Found. Comput. Sci., 29(5):825-843 (2018) (doi) (pdf)

(A.30) Saarela:
Studying word equations by a method of weighted frequencies.
Fund. Inform., 162(2-3):223-235 (2018) (doi) (pdf)

(A.29) Nowotka, Saarela:
An optimal bound on the solution sets of one-variable word equations and its consequences.
Proceedings of the 45th ICALP, LIPIcs 107:136:1-136:13, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik (2018) (doi) (arXiv) (Journal version in A.39)

2017

(A.28) Saarela:
Palindromic length in free monoids and free groups.
Proceedings of the 11th WORDS, LNCS 10432:203-213, Springer (2017) (doi) (pdf)

(A.27) Cassaigne, Karhumäki, Saarela:
On growth and fluctuation of k-abelian complexity.
European J. Combin., 65:92-105 (2017) (doi) (pdf)

(D.02) Karhumäki, Matiyasevich, Saarela:
Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics.
TUCS Lecture Notes 26 (2017) (link)

(B.04) Karhumäki, Saarela, Zamboni:
Variations of the Morse-Hedlund theorem for k-abelian equivalence.
Acta Cybernet., 23(1):175-189 (2017) (doi) (pdf)

(A.26) Saarela:
Word equations where a power equals a product of powers.
Proceedings of the 34th STACS, LIPIcs 66:55:1-55:9, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik (2017) (doi) (Journal version in A.33)

2016

(A.25) Nowotka, Saarela:
A connection between one-unknown word equations and constant-free three-unknown word equations.
Proceedings of the 20th DLT, LNCS 9840:332-343, Springer (2016) (doi) (Journal version in A.32)

(A.24) Endrullis, Karhumäki, Klop, Saarela:
Degrees of infinite words, polynomials and atoms.
Proceedings of the 20th DLT, LNCS 9840:164-176, Springer (2016) (doi) (Journal version in A.31)

(A.23) Saarela:
Equivalence relations defined by numbers of occurrences of factors.
Fund. Inform., 145(3):385-397 (2016) (doi) (pdf)

(D.01) Karhumäki, Saarela:
Proceedings of the Finnish Mathematical Days 2016.
TUCS Lecture Notes 25 (2016)

2015

(B.03) Endrullis, Klop, Saarela, Whiteland:
Degrees of transducibility.
Proceedings of the 10th WORDS, LNCS 9304:1-13, Springer (2015) (doi) (pdf) (Related to an invited talk given by J. Endrullis)

(A.22) Cassaigne, Karhumäki, Saarela:
On growth and fluctuation of k-abelian complexity.
Proceedings of the 10th CSR, LNCS 9139:109-122, Springer (2015) (doi) (Journal version in A.27)

(A.21) Saarela:
Systems of word equations, polynomials and linear algebra: A new approach.
European J. Combin., 47:1-14 (2015) (doi) (arXiv)

2014

(A.20) Mercas, Saarela:
5-abelian cubes are avoidable on binary alphabets.
RAIRO Inform. Theor. Appl., 48(4):467-478 (2014) (doi) (pdf)

(B.02) Saarela:
Equivalence relations defined by numbers of occurrences of factors.
Proceedings of the 3rd RuFiDiM (2014) (Journal version in A.23)

(A.19) Karhumäki, Saarela, Zamboni:
Variations of the Morse-Hedlund theorem for k-abelian equivalence.
Proceedings of the 18th DLT, LNCS 8633:203-214, Springer (2014) (doi) (Journal version in B.04)

2013

(A.18) Karhumäki, Puzynina, Saarela:
Fine and Wilf's theorem for k-abelian periods.
Internat. J. Found. Comput. Sci., 24(7):1135-1152 (2013) (doi) (pdf)

(A.17) Karhumäki, Saarela, Zamboni:
On a generalization of Abelian equivalence and complexity of infinite words.
J. Combin. Theory Ser. A, 120(8):2189-2206 (2013) (doi) (arXiv)

(A.16) Saarela:
Weakly unambiguous morphisms with respect to sets of patterns with constants.
Proceedings of the 9th WORDS, LNCS 8079:229-237, Springer (2013) (doi) (pdf)

(A.15) Huova, Saarela:
Strongly k-abelian repetitions.
Proceedings of the 9th WORDS, LNCS 8079:161-168, Springer (2013) (doi) (pdf)

(A.14) Mercas, Saarela:
3-abelian cubes are avoidable on binary alphabets.
Proceedings of the 17th DLT, LNCS 7907:374-383, Springer (2013) (doi) (pdf)

2012

(B.01) Mercas, Saarela:
5-abelian cubes are avoidable on binary alphabets.
Proceedings of the 14th Mons Days (2012) (Journal version in A.20)

(A.13) Huova, Karhumäki, Saarela:
Problems in between words and abelian words: k-abelian avoidability.
Theoret. Comput. Sci., 454:172-177 (2012) (doi) (pdf)

(A.12) Karhumäki, Puzynina, Saarela:
Fine and Wilf's theorem for k-abelian periods.
Proceedings of the 16th DLT, LNCS 7410:296-307, Springer (2012) (doi) (Journal version in A.18)

(G.03) Saarela:
Word equations and related topics: independence, decidability and characterizations.
Doctoral dissertation, University of Turku (2012) (link) (pdf) (Based on A.01, A.04, A.08, A.09, A.10 and A.11)

2011

(A.11) Karhumäki, Saarela:
The unique decipherability in the monoid of regular languages is undecidable.
Fund. Inform., 110(1-4):197-200 (2011) (doi) (pdf)

(A.10) Saarela:
Systems of word equations and polynomials: a new approach.
Proceedings of the 8th WORDS, EPTCS 63:215-225 (2011) (doi) (Journal version in A.21)

(A.09) Karhumäki, Saarela:
On maximal chains of systems of word equations.
Proc. Steklov Inst. Math., 274:116-123 (2011) (doi) (arXiv)

(A.08) Saarela:
Unique decipherability in the additive monoid of sets of numbers.
RAIRO Inform. Theor. Appl., 45(2):225-234 (2011) (doi) (pdf)

(A.07) Huova, Karhumäki, Saarela, Saari:
Local squares, periodicity and finite automata.
In Calude, Cristian and Rozenberg, Grzegorz and Salomaa, Arto (editors), Rainbow of Computer Science, LNCS 6570:90-101, Springer (2011) (doi) (pdf)

2010

(A.06) Karhumäki, Saarela:
Noneffective regularity of equality languages and bounded delay morphisms.
Discrete Math. Theor. Comput. Sci., 12(4):9-18 (2010) (pdf)

2009

(A.05) Saarela:
Ultimately constant abelian complexity of infinite words.
J. Autom. Lang. Comb., 14(3-4):255-258 (2009) (pdf)

(A.04) Saarela:
On the complexity of Hmelevskii's theorem and satisfiability of three unknown equations.
Proceedings of the 13th DLT, LNCS 5583:443-453, Springer (2009) (doi)

(A.03) Karhumäki, Saarela:
Noneffective regularity of equality languages and bounded delay morphisms.
Proceedings of the conference AutoMathA 2009 (2009) (Journal version in A.06)

(G.02) Saarela:
A new proof of Hmelevskii's theorem.
Licentiate thesis, University of Turku (2009) (pdf)

2008

(A.02) Saarela, Ekberg, Nyberg:
Random beacon for privacy and group security.
Proceedings of the 4th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, 514-519 (2008) (doi) (pdf)

(A.01) Karhumäki, Saarela:
An analysis and a reproof of Hmelevskii's theorem.
Proceedings of the 12th DLT, LNCS 5257:467-478, Springer (2008) (doi)

2007

(G.01) Saarela:
Sanayhtälöiden parametriset ratkaisut.
Master's thesis, University of Turku (2007) (pdf)