• English
    • français
  • English 
    • English
    • français
View Item 
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Unary patterns under permutations

Thumbnail

View Open

Unary_patterns_under_permutations.pdf (352.7Kb)

Metadata

Show full item record

Author

Currie, James D.
Nowotka, Dirk
Manea, Florin
Reshadi, Kamellia

Uri

http://hdl.handle.net/10680/1762

Date

2018-06-04

Doi

10.1016/j.tcs.2018.05.033

Citation

Theor. Comput. Sci. 743: 72-82 (2018)

Abstract

Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, and other questions of recent interest. Unary patterns with permutations have been previously analysed only for lengths up to 3. Consider a pattern $p=\pi_{i_1}(x)\ldots \pi_{i_r}(x)$, with $r\geq 4$, $x$ a word variable over an alphabet $\Sigma$ and $\pi_{i_j}$ function variables, to be replaced by morphic or antimorphic permutations of $\Sigma$. If $|\Sigma|\ge 3$, we show the existence of an infinite word avoiding all pattern instances having $|x|\geq 2$. If $|\Sigma|=3$ and all $\pi_{i_j}$ are powers of a single morphic or antimorphic $\pi$, the length restriction is removed. For the case when $\pi$ is morphic, the length dependency can be removed also for $|\Sigma|=4$, but not for $|\Sigma|=5$, as the pattern $x\pi^2(x)\pi^{56}(x)\pi^{33}(x)$ becomes unavoidable. Thus, in general, the restriction on $x$ cannot be removed, even for powers of morphic permutations. Moreover, we show that for every positive integer $n$ there exists $N$ and a pattern $\pi^{i_1}(x)\ldots \pi^{i_n}(x)$ which is unavoidable over all alphabets $\Sigma$ with at least $N$ letters and $\pi$ morphic or antimorphic permutation.

Collections

  • James D. Currie

Report a copyright concern

Contact Us | Send Feedback
 

 

Browse

All of WinnSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Report a copyright concern

Contact Us | Send Feedback