{"entities":{"Q490909":{"pageid":492676,"ns":120,"title":"Item:Q490909","lastrevid":62232720,"modified":"2026-04-11T04:40:46Z","type":"item","id":"Q490909","labels":{"en":{"language":"en","value":"Generalized trapezoidal words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6474825"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$70CC32C1-9080-4B1A-8763-9AD74EC47648","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d8d83ff88111e26023b3e23c88634f2fee6f298","datavalue":{"value":{"text":"Generalized trapezoidal words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490909$120D1C39-DC32-4AE5-B6A2-1DA5F4F11889","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0db1fee8a8577f6a7f457a06c2ec73cfe2f00ae6","datavalue":{"value":"1343.68187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490909$49DD0B9B-458A-4BFC-ABDE-BD0BC41A14D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be4996b22052fc7a0a8cdf45c097a578d8121954","datavalue":{"value":{"entity-type":"item","numeric-id":391313,"id":"Q391313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$F677CC47-E4BE-47A7-AE22-20DD4E0FE87B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb343ba71ab38a538058d63e0dd495107e9891cb","datavalue":{"value":{"entity-type":"item","numeric-id":223811,"id":"Q223811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$D297800E-A548-42FF-A16B-991A68F30862","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$0BD18053-B8DC-43E4-B17C-E6309450FD86","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e463a3f76b72914d69100f109f02e2f624263f82","datavalue":{"value":{"time":"+2015-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490909$C492C65A-E8DC-49B1-95FB-F8ACAE0A24F1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b09da655fac33c0e2c873148a516c3baecfda8af","datavalue":{"value":"https://arxiv.org/abs/1408.0451","type":"string"},"datatype":"url"},"type":"statement","id":"Q490909$D1B0BCBF-3066-4B79-A66B-9C97A538A44D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dac3c5e812a83cb64d4f95dc596166bc33ded209","datavalue":{"value":"The factor complexity \\(C_w(n)\\) of a word \\(w\\) of length \\(\\ell\\) is the function that, for each \\(n\\in\\{0,1,\\dots,\\ell\\}\\), returns the number of distinct factors of \\(w\\) of length \\(n\\). The word \\(w\\) is called trapezoidal if \\(C_w(n)\\) increases by 1 for each \\(n\\) in the interval \\([0,r]\\) for some \\(r\\leq\\ell/2\\), is constant for each \\(n\\) in the interval \\([r,\\ell-r]\\), and decreases by 1 for each \\(n\\) in the interval \\([\\ell-r,\\ell]\\). Any trapezoidal word is necessarily over a binary alphabet.   The authors suggest the following generalization. A word \\(w\\) of length \\(\\ell\\) is called a generalized trapezoidal word (GT-word) if there exist positive integers \\(m, M\\) with \\(m\\leq M\\leq\\ell\\) such that \\(C_w(n)\\) increases by 1 for each \\(n\\) in the interval \\([1,m]\\), is constant for each \\(n\\) in the interval \\([m,M]\\), and decreases by 1 for each \\(n\\) in the interval \\([M,\\ell]\\). GT-words exist over any alphabet and the binary GT-words are precisely the trapezoidal words. The first main result of the paper (Theorem 17) nicely characterizes GT-words in terms of their hearts where the heart of a word \\(w\\) that contains at least two occurrences of some letter is the unique factor of \\(w\\) that remains if one erases the longest prefix and the longest suffix of \\(w\\) that contain letters only occurring once in \\(w\\).   A word of length \\(\\ell\\) is rich if it has \\(\\ell+1\\) distinct palindromic factors. The second main result (Theorem 27) gives a complete characterization of the rich GT-words in terms of the hearts and the longest palindromic prefixes and suffixes of the hearts; its proof in the paper is very technical.","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$5CAD19AF-C483-46A0-8911-E7398B1F3ECA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490909$8CD4B96C-CD60-4315-ABF9-10729599A769","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9bb3bf8993aa3be4520cd5124526c8978ea612df","datavalue":{"value":"6474825","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490909$31DF4C7E-3981-4603-8589-F48F56DFB3F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e800a7b30cf174bf647e50618a644756839f08f","datavalue":{"value":"word complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$C9AD7482-2142-4297-A1AF-4064FAF29F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4901c25ec95e71deaaab01bc69cb2ad067fda983","datavalue":{"value":"trapezoidal word","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$307AE2B3-680A-4084-BE43-CCA11CEBE182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"042c9dd8130b47f07ecf20c27591343651726b2c","datavalue":{"value":"generalized trapezoidal word","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$B8180BC9-E52A-4B8C-ADA1-8A86047C7B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"376c5ba6db3848c5b96f358f8e703e6e621d9889","datavalue":{"value":"Sturmian word","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$24BA81C2-50A6-4BA9-BAD0-FA8D73EAD775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91219724b1d31edcda7c6d1509916c91d64ae88c","datavalue":{"value":"palindrome","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$0512E7E1-F1CE-4BAF-9DBE-1215BCF2C987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d78fe9e609b78e2d96ccf1ddb7c0c84cbeedd4b9","datavalue":{"value":"rich word","type":"string"},"datatype":"string"},"type":"statement","id":"Q490909$1827BE10-5432-4589-BB55-F67C468815E3","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$5671E4DB-D42F-4F16-B553-541B84E74130","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c081048e18da575cd03e51a2f0f4a4e490d64cc1","datavalue":{"value":"W1514144651","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490909$CA1B4A51-0F0C-43F0-92ED-3CF0765D10F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e58f1108d07a99592426505bb823948dca430252","datavalue":{"value":{"entity-type":"item","numeric-id":3021999,"id":"Q3021999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$64E0787A-2B1E-4271-BFCD-E2685B504E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18f64a6219ee63f9b8a3f52f98f9e2b0058dd20f","datavalue":{"value":{"entity-type":"item","numeric-id":1935783,"id":"Q1935783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$0FAAF41F-E700-4CAF-8619-C8C1E8F8F541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b49d4842c85408c5b90b0bc959be592c0ee0530","datavalue":{"value":{"entity-type":"item","numeric-id":1605325,"id":"Q1605325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$D068F542-459F-4474-86B4-8D65CC4E2E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a94dee70a6fa7dc8bc56fc3835784af5332a0f20","datavalue":{"value":{"entity-type":"item","numeric-id":1292479,"id":"Q1292479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$3B3DF598-226D-4C35-BBCF-B74D5139D2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d96c04e39bcf4d3d6a7816d49ef93c64f709808d","datavalue":{"value":{"entity-type":"item","numeric-id":955036,"id":"Q955036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$8ACC22C7-2074-4A71-A72C-3B89796A4FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13fc59de1056ba247b8df3c3afb993eacda84d8","datavalue":{"value":{"entity-type":"item","numeric-id":5941085,"id":"Q5941085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$78AB8D28-44D4-4219-9183-DF2292D99A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b44a933c195fa38c102b4dabe2b7759468f9ef9","datavalue":{"value":{"entity-type":"item","numeric-id":1960407,"id":"Q1960407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$DC6DE8EF-F0C6-460B-B99B-1ADA04F84243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb35b70526cb77e3d62135b1841d5ade6f0ca6c4","datavalue":{"value":{"entity-type":"item","numeric-id":1003605,"id":"Q1003605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$07F380CA-C1E3-4D35-A131-A59877FE36E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb423d88b02a3fd1f625a729e701748210dc1931","datavalue":{"value":{"entity-type":"item","numeric-id":1606164,"id":"Q1606164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$D3348F3E-DDD2-4F8B-8C62-DA3E1C416657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490909$9DE50260-6A55-47AA-A13D-7933F166BE42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d6bd25e32020293f3e0bca5703cc9aa6db1800b6","datavalue":{"value":"10.1016/J.JCTA.2015.06.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490909$093040FF-9F03-4F6D-B520-F18B1F809168","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35e0653fb29bf12171d177abffc7c29e8b8f60aa","datavalue":{"value":{"entity-type":"item","numeric-id":955036,"id":"Q955036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7656fcf493dad9b00be8b96128952406173a891a","datavalue":{"value":{"amount":"+0.8708350658416748","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490909$B760508C-C900-47A0-9DEF-B052A1A65F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"191372fdd21169dd5eb382be2640851df524fb52","datavalue":{"value":{"entity-type":"item","numeric-id":1605325,"id":"Q1605325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daf824476dd666595f6c27cd00657ca831256701","datavalue":{"value":{"amount":"+0.8568194508552551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490909$FBBFAC17-820A-4596-8684-BAB33D6B6638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75e3e9f723d0a65e4b2ed65ed461bd2a7fd1b657","datavalue":{"value":{"entity-type":"item","numeric-id":2789522,"id":"Q2789522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d8006fee571091e5730d7a4fc8c188272706a42","datavalue":{"value":{"amount":"+0.847667396068573","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490909$82E8185F-4FD3-4DBB-9F47-267C7CED552C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eac599ed0e62490c0a61149940ad2674f84725d","datavalue":{"value":{"entity-type":"item","numeric-id":1935783,"id":"Q1935783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a4391d6b5523479df4ee7a9972741c3833ee5a3","datavalue":{"value":{"amount":"+0.8381327390670776","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490909$33A54EC3-797C-42CA-A167-4215EDFCE023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aec70bf4edcc97d8b4495806ad3d629490c5d0db","datavalue":{"value":{"entity-type":"item","numeric-id":2333038,"id":"Q2333038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fd4b300bd3a59b7025a4709a92e012a577d0fc0","datavalue":{"value":{"amount":"+0.7860806584358215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490909$2944BE84-42F2-40AE-B327-63D524E62E62","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized trapezoidal words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_trapezoidal_words"}}}}}