Preprints

• A. Frid, D. Jamet, The number of binary rotation words, submitted. ArXiv preprint. Also reported at Journées Montoises 2012. Conference abstract, slides.

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

2013

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

  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. 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. Preliminary version, 221 kb.

  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. PS(210kb) of the preliminary version.

  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. Informatics Appl. 40 (2006) 443--458. Preliminary version, PS (301kb). Also reported at WACaM04 (an invited talk), presentation (PPT, 270kb).

  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. Informatics Appl. 40 (2006), 569--582. Preliminary version, PDF(201kb).

  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. Abstract and links.

  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. preliminary version, PS (425kb).

  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, PS.

  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. Preliminary version, PS(199kb). 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. preliminary version, PS(170kb).

  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. PS(152kb)

  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. PDF.

  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. PS(170kb)

  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.)

  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, PDF. 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. PDF.

  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. PS (192kb)

  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. PS (119kb)

  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".