Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences
We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those n for which an automatic sequence x has a closed (res...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
European Mathematical Information Service (EMIS)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103037 https://orcid.org/0000-0001-6823-3343 |
| _version_ | 1826211132677816320 |
|---|---|
| author | Schaeffer, Luke R. Shallit, Jeffrey |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Schaeffer, Luke R. Shallit, Jeffrey |
| author_sort | Schaeffer, Luke R. |
| collection | MIT |
| description | We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those n for which an automatic sequence x has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length n is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length n of a k-automatic sequence is not k-synchronized. |
| first_indexed | 2024-09-23T15:01:06Z |
| format | Article |
| id | mit-1721.1/103037 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:01:06Z |
| publishDate | 2016 |
| publisher | European Mathematical Information Service (EMIS) |
| record_format | dspace |
| spelling | mit-1721.1/1030372022-09-29T12:06:38Z Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences Schaeffer, Luke R. Shallit, Jeffrey Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Schaeffer, Luke R. We prove that the property of being closed (resp., palindromic, rich, privileged trapezoidal, balanced) is expressible in first-order logic for automatic (and some related) sequences. It therefore follows that the characteristic function of those n for which an automatic sequence x has a closed (resp., palindromic, privileged, rich, trapezoidal, balanced) factor of length n is itself automatic. For privileged words this requires a new characterization of the privileged property. We compute the corresponding characteristic functions for various famous sequences, such as the Thue-Morse sequence, the Rudin-Shapiro sequence, the ordinary paperfolding sequence, the period-doubling sequence, and the Fibonacci sequence. Finally, we also show that the function counting the total number of palindromic factors in the prefix of length n of a k-automatic sequence is not k-synchronized. 2016-06-07T15:42:05Z 2016-06-07T15:42:05Z 2016-02 2015-12 Article http://purl.org/eprint/type/JournalArticle 1077-8926 1097-1440 http://hdl.handle.net/1721.1/103037 Schaeffer, Luke, and Jeffrey Shallit. "Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences." Electronic Journal of Combinatorics, 23:1 (2016), pp. 1-19. https://orcid.org/0000-0001-6823-3343 en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p25 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf European Mathematical Information Service (EMIS) European Mathematical Information Service (EMIS) |
| spellingShingle | Schaeffer, Luke R. Shallit, Jeffrey Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences |
| title | Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences |
| title_full | Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences |
| title_fullStr | Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences |
| title_full_unstemmed | Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences |
| title_short | Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences |
| title_sort | closed palindromic rich privileged trapezoidal and balanced words in automatic sequences |
| url | http://hdl.handle.net/1721.1/103037 https://orcid.org/0000-0001-6823-3343 |
| work_keys_str_mv | AT schaefferluker closedpalindromicrichprivilegedtrapezoidalandbalancedwordsinautomaticsequences AT shallitjeffrey closedpalindromicrichprivilegedtrapezoidalandbalancedwordsinautomaticsequences |