2022

• D. Bulgakova, A. E. Frid, J. Scanvic, Prefix palindromic length of the Sierpinski word, DLT 2022: 78-89 ArXiv preprint.

  We find the prefix palindromic length of the Sierpinski word and an automaton describing its first differences.

• A. E. Frid, J. Scanvic, An upper bound for the number of palindromic length profiles of binary words, Talk at Journées Montoises 2022. Slides

  We find a set of factors which never appear in the sequence of first differences of the prefix palindromic length of a binary word and conjecture that all the other words do appear in such a sequence.

2021

• A. E. Frid, E. Laborde, J. Peltomäki, On prefix palindromic length of automatic words, Theoret. Comput. Sci. 891 (2021) 13-23. Journal page, ArXiv preprint.

  We prove that the prefix palindromic length of a k-automatic word containing a finite number of distinct palindromes is k-regular, and find precisely this function for the paperfolding word and for the Rudin-Shapiro word. We also conjecture that for the period-doubling word and for the Fibonacci word, it is not regular.

2020

• M. Andrieu, A. E. Frid, Morphic words and equidistributed sequences. Theoret. Comput. Sci. 804 (2020), 171-185. Journal page, ArXiv preprint.

  We discuss numeric sequences arising from the measure of shifts of a pure morphic infinite word, and construct them with morphisms. A software tool for that, written by M. Andrieu, is provided here.

2019

• J. Cassaigne, A. Frid, S. Puzynina, L. Q. Zamboni, Cost and dimension of words of zero topological entropy. Bull. SMF 147 (2019), 639-660. Journal page, arXiv preprint (containing the results of two papers).

  A continuation of the result on linear complexity published in Proc. AMS earlier the same year. A series of results on words of low complexity and decompositions of their factors.

• A. E. Frid, Prefix palindromic length of the Thue-Morse word. Journal of Integer Sequences, Vol. 22 (2019), Article 19.7.8. Journal page.

  In addition to the precise formula for the prefix palindromic length of the Thue-Morse word, the paper contains a discussion of several open problems. For example, the ppl of the Thue-Morse word, which is 2-automatic, is a 2-regular sequence. But is the analogous statement true for all k-automatic words?

• A. E. Frid, First lower bounds on palindromic length. Proc. DLT 2019, LNCS 11647, Springer, 2019, pp. 234--243. Slides.

  The paper contains an announcement of the precise formula for the prefix palindromic length of the Thue-Morse word (proven in detail in the journal paper above), some lower bounds for Toeplitz words and a discussion.

• J. Cassaigne, A. Frid, S. Puzynina, L. Q. Zamboni, A characterization of words of linear complexity. Proc. AMS 147 (2019), 3103-3115.

  The main theorem can be stated as follows: an infinite word is of linear factor complexity if and only if its language of factors is a subset of ST, where S and T are languages of bounded complexity. Continued in the Bull. SMF paper later the same year; the preprint containing the results of both papers is here.

• P. Bonardo, A. E. Frid, J. Shallit, The number of valid factorizations of Fibonacci prefixes. Theoret. Comput. Sci. 775 (2019) 68-75. Journal page, ArXiv preprint.

  We establish several recurrence relations and an explicit formula for V(n), the number of factorizations of the length-n prefix of the Fibonacci word into a (not necessarily strictly) decreasing sequence of standard Fibonacci words (OEIS sequence A300066). In particular, we show that the sequence V(n) is the shuffle of the ceilings of two linear functions of n. We also establish Fibonacci-regular properties of the sequence.

• A. E. Frid, Quelques méthodes pour les mots sturmiens. Book chapter, in: J. Chalopin et P. Guillon (eds), Informatique mathématique : Une photographie en 2019. CNRS Editions, 2019, pp. 35-64. Draft (in French). A raw English draft also exists, write me to get it.

  Main techniques described in the chapter are, first, the geometric dual method of Berstel and Pocchiola, and second, the description of palindromes in a characteristic Sturmian word by the respective Ostrowski numeration system.

2018

• A. E. Frid, Sturmian numeration systems and decompositions to palindromes. European J. Combin. 71 (2018) 202-212. Journal paper. ArXiv preprint.

  We extend Ostrowski numeration systems and allow a wider range of coefficients to better reflect the structure of the associated characteristic Sturmian words. In particular, it allows to prove for Sturmian words the conjecture on the palindromic length from the 2013 paper by Puzynina, Zamboni and the author (see below).

• A. E. Frid, Representations of palindromes in the Fibonacci word. Proc. of Numeration 2018. Book of abstracts, p. 9-12.

  We consider palindromes in the Fibonacci word in terms of the Zeckendorf representations of their ends. In particular, we prove an upper bound for the number of palindromes necessary to construct the Fibonacci prefix of length n and conjecture which prefixes are the shortest with a given number of palindromes.

2017

• S. V. Avgustinovich, A. E. Frid, S. Puzynina, Minimal complexity of equidistributed infinite permutations, European J. Combin. 65 (2017) 24-36. Journal page, ArXiv preprint.

  In the paper we introduce a new notion of an equidistributed infinite permutation, i.e., an infinite permutation which can be defined by a representative which is an equidistributed sequence of numbers from [0,1]. We show that the minimal complexity of an equidistributed permutation is p(n)=n, and that the class of equidistributed permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

2015

• S. V. Avgustinovich, A. E. Frid, S. Puzynina, Canonical representatives of morphic permutations, Proc. WORDS 2015, LNCS V. 9304, 59-72.

  In the paper we construct equidistributed sequences of real numbers between 0 and 1 such that the ordering of these numbers is exactly the lexicographic order of shifts of a fixed point of a morphism of a specific family. Thus, the result is a generalisation of a 2009 construction for the Thue-Morse word by Makarov.

• S. V. Avgustinovich, A. E. Frid, S. Puzynina, Ergodic infinite permutations of minimal complexity, Proc. DLT 2015, LNCS V. 9168, 2015, 71-84.

  A preliminary version of the paper Minimal complexity of equidistributed infinite permutations, see above.

2014

• A. Frid, D. Jamet, The number of binary rotation words, RAIRO-Theor. Inf. Appl. 48 (2014) 453-465. Journal page, ArXiv preprint. Also reported at Journées Montoises 2012.

  We give a precise formula for the number of binary rotation words.

• J. Cassaigne, A. Frid, S. Puzynina, L. Q. Zamboni, Subword complexity and decomposition of the set of factors, Proc. MFCS 2014, LNCS V. 8634, 2014, 147-158. Springer reference.

  This paper is revised and extended to the 2019 papers in Proc. AMS and Bull. SMF.

2013

• A. E. Frid, S. Puzynina, L. Zamboni, On palindromic factorization of words, Advances in Appl. Math. 50 (2013) 737-748. Journal reference, preprint.

  We state the following conjecture: is it true that for any P in any non-periodic infinite word there exists a factor not equal to a catenation of at most P palindromes? We prove this conjecture for the case of k-power-free words and for some more general case when the so-called (k,l)-condition is fulfilled.

2012

• A. E. Frid, Fine and Wilf's theorem for permutations, Siberian Electronic Mathematical Reports 9 (2012) 377-381, PDF.

  We show that the famous Fine and Wilf's theorem for periodic words can be extended to permutations only partially, in the case of coprime periods. If the periods are not coprime, we can prove another statement instead.

• A. Frid, L. Zamboni, On automatic infinite permutations. Theoret. Inf. Appl. 46 (2012) P. 77-85. Journal link, preprint.

  We consider three possible definitions of an automatic permutation analogous to those for an automatic word, and show that they are not equivalent, unlike the case of words. We study also the inclusion relations between some of the definitions.

2011

• P. Ambrož, A. Frid, Z. Masáková, E. Pelantová, On the number of factors in codings of three interval exchange, Discrete Mathematics and Theoretical Computer Science Vol 13, No 3 (2011), P. 51-66. Full text.

  We give the upper and lower bounds for the number of all 3-interval exchange words. They both grow as n⁴ and differ approximately in 6 times.

• S. V. Avgustinovich, A. Frid, T. Kamae, P. Salimov, Infinite permutations of lowest maximal pattern complexity, Theoretical Computer Science 412 (2011) 2911-2921. Journal page, preprint.

  We define the maximal pattern complexity of an infinite permutation analogously to that for words defined by T. Kamae and L. Zamboni in 2002. The least possible complexity for words is 2n, but no characterization of the words of complexity 2n is known. We prove that the minimal complexity for permutations is n and caracterize the permutations of minimal complexity, which turn out to be strongly related to Sturmian words.

• J. Cassaigne, A. Frid, F. Petrov, On possible growth of Toeplitz languages, Siberian Mathematical Journal 52 (2011) 81-94 (in Russian). Preprint in English.

  We consider the complexity of factorial languages obtained by applying several simple Toeplitz patterns (=uniform morphisms of a special form) in an arbitrary order. The complexity turns out to be subpolynomial, its degree can be found as a solution of a transcendental equation. Using analytic methods, we find the precise asymptotics for the complexity.

2009

• A. Frid, Simple equations on binary factorial languages, Theoret. Comput. Sci. 410 (2009), P. 2947-2956. Journal page.

  The extended version of the 2007 paper on commutation of binary factorial languages. Several more equations are considered.

2007

• A. Frid, Commutation of Binary Factorial Languages, in: Developments in Language Theory, LNCS 4588, 2007. P. 193-204.

  We completely solve the commutation equation XY=YX on binary factorial languages using the unique decomposition theorem (see a 2005 paper on it). The extended version of the paper appeared in 2009.

• A. Frid, Canonical decomposition of a catenation of factorial languages, Siberian Electronic Mathematical Reports 4 (2007) 12--19, PDF.

  A description of the form of a canonical decomposition of a catenation of two languages whose canonical decompositions are known. A tool for the next papers on equations on factorial languages, based on the 2005 paper on the canonical decompositions.

• J. Cassaigne, A. E. Frid. On arithmetical complexity of Sturmian words, Theoret. Comput. Sci. 380 (2007), 304-316. Journal page.

  The upper bound on the arithmetical complexity of a Sturmian word (=the number of rotation words with a given intervals), and precise formulas for the intervals between 1/3 and 2/3. The geometric technique by Berstel and Pocchiola is used. See also a lower bound in a 2005 paper.

• D.G. Fon-Der-Flaass, A.E. Frid, On periodicity and low complexity of infinite permutations, European Journal of Combinatorics 28 (2007), 2106-2114. Journal page.

  The full text of the 2005 paper on infinite permutations.

2006

• S. V. Avgustinovich, A. E. Frid, Canonical decomposition of a regular factorial language, Proc. CSR'06, LNCS 3967, P. 18-22.

  We answer a question by Yu. L. Yershov and prove that the factors of a canonical decomposition of a regular factorial language are regular and can be found from the automaton recognizing the initial language.

• A. E. Frid. On possible growths of arithmetical complexity, Theoret. Inf. Appl. 40 (2006) 443--458. Journal page.

  We use simple Toeplitz patterns to build a reach family of uniformly recurrent words whose arithmetical complexity grows subpolynomially and depends on the subword complexity of some directive sequence.

• S. V. Avgustinovich, J. Cassaigne, A. E. Frid. Sequences of low arithmetical complexity, Theoret. Inf. Appl. 40 (2006), 569--582. Journal page.

  We find uniformly recurrent words whose arithmetical complexity is the least possible. They are Toeplitz words generalizing the period doubling word.

2005

• D. G. Fon-Der-Flaass, A. E. Frid, On periodicity and low complexity of infinite permutations, DMTCS proceedings of EUROCOMB'05, DMTCS proc. AE, 2005, p. 267--272. Journal page.

  The first talk on infinite permutations. A shorter version of the paper from Europ. J. Combin., see papers dated 2007.

• A. E. Frid. Sequences of linear arithmetical complexity, Theoret. Comput. Sci. 339 (2005) 68--87. Journal page.

  A characterization of uniformly recurrent words of linear arithmetical complexity. Reported already at WORDS 2003 in Turku. 3rd Euler prize in 2007.

• A. E. Frid. A lower bound for the arithmetical complexity of Sturmian words // Siberian Electronic Mathematical Reports 2 (2005) pp. 14-22. [Russian, English abstract]. PDF.

  Indeed, a cubic lower bound for the arithmetical complexity of a Sturmian word, which can be also interpreted as the number of rotation words with a given interval. Complements the 2007 joint paper with J. Cassaigne containing the upper bound and some precise formulas.

• S. V. Avgustinovich, A. E. Frid. A unique decomposition theorem for factorial languages. International Journal of Algebra and Computation 15 (2005) 149--160. Journal page.

  The first paper on canonical decompositions of factorial languages. We prove existence and uniqueness of the canonical decomposition of a factorial language to a catenation of factorial languages.

2003

• A. E. Frid. Arithmetical complexity of symmetric D0L words, Theoret. Comput. Sci. 306 (2003) 535-542. Journal page.

  We find the arithmetical complexity of fixed points of all symmetric morphisms, generalizing the previous result on the Thue-Morse word. In particular we prove that this complexity is either exponential or ultimately constant (when the word is periodic).

2002

• S. V. Avgustinovich, A. E. Frid. Words avoiding abelian inclusions. Journal of Automata, Languages and Combinatorics 7 (2002) 3-9. Journal file

  We consider two possible extensions of the notion of an abelian square and prove that one of them is unavoidable and the other one is avoidable. In particular, we rediscover yet another time that "approximate" abelian powers are unavoidable.

2001

• S. V. Avgustinovich, O. V. Borodin, A. E. Frid. Distributive colorings of plane triangulations of minimal degree 5. Diskr.analiz i issl. operacii 8 (2001), no. 1, p. 3-16 (in Russian). PDF.

  We describe maximal matrices of distributive colorings of planar triangulations of minimal degree 5 into 2 colors.

• A. E. Frid. Overlap-Free Symmetric D0L words. DMTCS 4 (2001) no. 2, 357-362. Journal page.

  Answering to a question by J. Shallit, we prove that a fixed point of a symmetric morphisms such that all symbols in the image of each letter are distinct is overlap-free.

2000

• S. V. Avgustinovich, D. G. Fon-Der-Flaass, A. E. Frid. Arithmetical complexity of infinite words. in: Masami Ito and Teruo Imaoka, editors, Words, Languages & Combinatorics III, pp. 51-62, Singapore, 2003. World Scientific Publishing, 2003. ICWLC 2000, Kyoto, Japan, March 14-18, 2000. Link.

  The first paper on arithmetical complexity, reported in 2000 and published in 2003. Includes the results on the arithmetical complexity of the Thue-Morse word and of the paperfolding word.

1999

• A. Frid. On factor graphs of DOL words. Diskr. analiz i issl. operacii 6 (1999), no. 4, p. 92-103 (in Russian). (English translation in: A. E. Frid, On factor graphs of D0L words, Discr. Appl. Math., 114 (2001) 121-130, journal page.)

  We completely describe the Rauzy graphs evolution in fixed points of "nice" uniform morphisms.

• A. Frid, S. V. Avgustinovich. On bispecial words and subword complexity of DOL sequences. Proceedings of SETA'98, DMTCS series, Springer (1999) 191-204.

  The results of this paper, rediscovered independently, give just a small refinement of some of 1997 results of J. Cassaigne, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 67-88, link. Later they were continued by K. Klouda (journal reference, preprint).

• A. Frid. Applying a uniform marked morphism to a word. DMTCS 3 (1999) no. 3, 125-140. Journal page.

  We completely describe how the subword complexity, the recurrence function, frequencies of factors etc. change after a "nice" morphism is applied to the word.

1998

• A. Frid. On the frequency of factors in a DOL word. Journal of Automata, Languages and Combinatorics, 3 (1998), no. 1, 29-41. PDF

  We discribed a new way to compute frequencies of factors in fixed points of morphisms and gave a complete description of frequencies in the fixed points of uniform marked morphisms in terms of frequency tables and their evolutions.

• A.Frid. The frequency of occurrence of factors in a DOL word. Diskr. analiz i issl. operacii, 5 (1998), no.1, 82-87 (in Russian).

  The results of this paper are covered by those of the paper in JALC written in English.

• A. Frid. On uniform DOL words. STACS'98, Lect. Notes Comp. Sci., 1373 (1998) 544-554. Link.

  We gave a criterion of circularity for the fixed points of uniform buffer morphisms and a precise formula for their subword complexity, both in the circular and in the uncircular cases.

1997

• A. Frid. The subword complexity of fixed points of binary uniform morphisms. FCT'97, Lect. Notes Comp. Sci., 1279 (1997) 178-187.

  The results of this paper are covered by those of the 1998 paper "On uniform DOL words".

• A. Frid. On the subword complexity of infinite words generated by morphisms. Diskr. analiz i issl. operacii, 4 (1997) no.1, 53-59 (in Russian). (English translation in: A. E. Frid, On the subword complexity of iteratively generated infinite words, Discr. Appl. Math. 114 (2001) 115-120.)

  The results of this paper are almost covered by those of the 1998 paper "On uniform DOL words".