Source author record

Stepan Starosta

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

5works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

Proof of Brlek-Reutenauer conjecture

Brlek and Reutenauer conjectured that any infinite word u with language closed under reversal satisfies the equality 2D(u) = \sum_{n=0}^{\infty}T_u(n) in which D(u) denotes the defect of u and T_u(n) denotes C_u(n+1)-C_u(n) +2 - P_U(n+1) - P_u(n), where C_u and P_u are the factor and palindromic complexity of u, respectively. This conjecture was verified for periodic words by Brlek and Reutenauer themselves. Using their results for periodic words, we have recently proved the conjecture for uniformly recurrent words. In the present article we prove the conjecture in its general version by a new method without exploiting the result for periodic words.

preprint2011arXiv

On Brlek-Reutenauer conjecture

Brlek and Reutenauer conjectured that any infinite word u with language closed under reversal satisfies the equality 2D(u)=\sum_{n=0}^{\infty} T(n) in which D(u) denotes the defect of u and T(n) denotes C(n+1)-C(n)+2-P(n+1)-P(n), where C and P are the factor and palindromic complexity of u, respectively. Brlek and Reutenauer verified their conjecture for periodic infinite words. We prove the conjecture for uniformly recurrent words. Moreover, we summarize results and some open problems related to defect, which may be useful for the proof of Brlek-Reutenauer Conjecture in full generality.

preprint2010arXiv

On Theta-palindromic Richness

In this paper we study generalization of the reversal mapping realized by an arbitrary involutory antimorphism $Θ$ . It generalizes the notion of a palindrome into a $Θ$ -palindrome -- a word invariant under $Θ$ . For languages closed under $Θ$ we give the relation between $Θ$ -palindromic complexity and factor complexity. We generalize the notion of richness to $Θ$ -richness and we prove analogous characterizations of words that are $Θ$ -rich, especially in the case of set of factors invariant under $Θ$ . A criterion for $Θ$ -richness of $Θ$ -episturmian words is given together with other examples of $Θ$ -rich words.

preprint2010arXiv

Sturmian Jungle (or Garden?) on Multiliteral Alphabets

The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We also collect many examples of infinite words to illustrate differences in the generalized definitions of Sturmian words.

preprint2009arXiv

Palindromes in infinite ternary words

We study infinite words u over an alphabet A satisfying the property P : P(n)+ P(n+1) = 1+ #A for any n in N, where P(n) denotes the number of palindromic factors of length n occurring in the language of u. We study also infinite words satisfying a stronger property PE: every palindrome of u has exactly one palindromic extension in u. For binary words, the properties P and PE coincide and these properties characterize Sturmian words, i.e., words with the complexity C(n)=n+1 for any n in N. In this paper, we focus on ternary infinite words with the language closed under reversal. For such words u, we prove that if C(n)=2n+1 for any n in N, then u satisfies the property P and moreover u is rich in palindromes. Also a sufficient condition for the property PE is given. We construct a word demonstrating that P on a ternary alphabet does not imply PE.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.