{"corpus_id":1244245,"paper_sha":"875e093e7b09a0d66551982dbd3c543435d69010","doi":"10.1016/j.tcs.2008.06.009","arxiv_id":"0802.3885","pmid":null,"pmcid":null,"mag_id":1979358057,"dblp_id":"journals/tcs/LucaGZ08","acl_id":null,"title":"Rich, Sturmian, and trapezoidal words","year":2008,"publication_date":"2008-02-26","venue":"Theoretical Computer Science","journal":{"name":"Theor. Comput. Sci.","pages":"569-573","volume":"407"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":16,"citation_count":30,"influential_citation_count":0,"is_open_access":false,"arxiv_categories":["math.CO","cs.DM"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":"Theoretical Computer Science 407 (2008) 569--573","mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity.","claims":[{"public_id":"cl_218475cb6afb8440f7be12932a96e161","status":"active","text":"Rich palindromes admit a characterization through a relation between palindromic complexity and subword complexity.","confidence":0.92,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_218475cb6afb8440f7be12932a96e161"},{"public_id":"cl_3176ae0faa755c5a07b450d8cb7d6552","status":"active","text":"Sturmian palindromes can also be characterized by their palindromic complexity.","confidence":0.93,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_3176ae0faa755c5a07b450d8cb7d6552"},{"public_id":"cl_5be7582dc03449aa03ab2973106819fb","status":"active","text":"Sturmian palindromes can be characterized by their subword complexity via the trapezoidal property.","confidence":0.94,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_5be7582dc03449aa03ab2973106819fb"},{"public_id":"cl_7c11c5c75a1448c6e063577b898ee6ce","status":"active","text":"The only trapezoidal palindromes are Sturmian.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_7c11c5c75a1448c6e063577b898ee6ce"}],"concepts":[{"public_id":"co_34d022523fc31910b4b7ae9859d9560b","status":"active","name":"trapezoidal words","description":"Finite words defined in terms of the trapezoidal behavior of subword complexity.","types":["word class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_34d022523fc31910b4b7ae9859d9560b"},{"public_id":"co_56b4fcb66f5e7eb01265c8983cb2245b","status":"active","name":"subword complexity","description":"The factor-counting complexity of a word as a function of factor length.","types":["complexity measure"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_56b4fcb66f5e7eb01265c8983cb2245b"},{"public_id":"co_689fcfeb396026fd7d98634dd1bd3c70","status":"active","name":"palindromes","description":"Words that read the same forward and backward.","types":["word property"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_689fcfeb396026fd7d98634dd1bd3c70"},{"public_id":"co_6fd670627fd1886a813e3978df0a0ba5","status":"active","name":"Sturmian words","description":"A class of finite or infinite words studied here in relation to palindromic and subword complexity.","types":["word class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_6fd670627fd1886a813e3978df0a0ba5"},{"public_id":"co_9aecad85b890a792366bf1eb3fa9c4e3","status":"active","name":"Sturmian palindromes","description":"Palindromes that belong to the Sturmian class of words.","types":["word class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_9aecad85b890a792366bf1eb3fa9c4e3"},{"public_id":"co_d4c25c44848a9896f52897061a2913af","status":"active","name":"rich palindromes","description":"Palindromic words with the maximal number of palindromic factors.","types":["word class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d4c25c44848a9896f52897061a2913af"},{"public_id":"co_da1c85a27a36fec96d4926f1aec0a78b","status":"active","name":"trapezoidal property","description":"A subword-complexity condition used to define trapezoidal words.","types":["property"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_da1c85a27a36fec96d4926f1aec0a78b"},{"public_id":"co_ec0b43a0bd453e0ea98dfca47256893e","status":"active","name":"rich words","description":"Finite or infinite words having the maximal possible number of palindromic factors.","types":["word class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ec0b43a0bd453e0ea98dfca47256893e"},{"public_id":"co_f34c307b1fd25781a9113b9cbc7e0f6f","status":"active","name":"palindromic complexity","description":"The number of palindromic factors of each length in a word.","types":["complexity measure"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_f34c307b1fd25781a9113b9cbc7e0f6f"}],"external_ids":{"DOI":"10.1016/j.tcs.2008.06.009","ArXiv":"0802.3885","PubMed":null,"PubMedCentral":null,"MAG":1979358057,"DBLP":"journals/tcs/LucaGZ08","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/0802.3885","landing_url":"https://arxiv.org/abs/0802.3885","source":"arxiv","pdf_url_source":"derived_arxiv","license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":637560,"paper_uid":"968f99ec-1064-4e07-8931-b2894078ac39","canonical_identity":{"paper_id":637560,"paper_uid":"968f99ec-1064-4e07-8931-b2894078ac39","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/1244245"}