20 citations · 86 across the 21 of their papers we have counts for
15 papers · 1 filter
Abelian Repetition Threshold Revisited
Elena A. Petrova, Arseny M. Shur
Abelian repetition threshold ART(k) is the number separating fractional Abelian powers which are avoidable and unavoidable over the k-letter alphabet. The exact values of ART(k) ar…
Branching Frequency and Markov Entropy of Repetition-Free Languages
Elena A. Petrova, Arseny M. Shur
We define a new quantitative measure for an arbitrary factorial language: the entropy of a random walk in the prefix tree associated with the language; we call it Markov entropy. W…
Transition Property For Cube-Free Words
Elena A. Petrova, Arseny M. Shur
We study cube-free words over arbitrary non-unary finite alphabets and prove the following structural property: for every pair of -ary cube-free words, if can be inf…
Subword complexity and power avoidance
Jeffrey Shallit, Arseny M. Shur
We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that -- the Thue-Morse word has the…
On the Combinatorics of Palindromes and Antipalindromes
Chuan Guo, Jeffrey Shallit, Arseny M. Shur
We prove a number of results on the structure and enumeration of palindromes and antipalindromes. In particular, we study conjugates of palindromes, palindromic pairs, rich words,…
Quantum, Stochastic, and Pseudo Stochastic Languages with Few States
Arseny M. Shur, Abuzer Yakaryilmaz
Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the s…