{"entities":{"Q1308983":{"pageid":1319733,"ns":120,"title":"Item:Q1308983","lastrevid":67361682,"modified":"2026-04-12T17:06:45Z","type":"item","id":"Q1308983","labels":{"en":{"language":"en","value":"On the starheight of some rational subsets closed under partial commutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 465564"}},"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":"Q1308983$DD1B3480-E749-4D58-8B79-5407A2F3F780","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"679ce0bf9c1fc3370a4c4791d5e484b005a68bc0","datavalue":{"value":{"text":"On the starheight of some rational subsets closed under partial commutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1308983$D73ABD51-304E-4283-914E-30D463F1BBD6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ecbf609037f19faee1c477d1c0cda098eb1e60a4","datavalue":{"value":"0789.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308983$96D319BE-9502-4D5A-8E8B-0B700B75E53D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa990e79bdd7ffcabe4f8d60711efd12e49a6fc6","datavalue":{"value":{"entity-type":"item","numeric-id":512187,"id":"Q512187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1308983$B9F976E8-14DC-4F5D-8311-F886DD0A313C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1308983$A212896F-38FB-4013-9A8C-6A39F1539A8E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5dc67d535c2692fb1fd5d6405cbd7a607dbc276b","datavalue":{"value":{"time":"+1994-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1308983$CB1AEAE2-94A9-4C5A-A6F7-47A5C2FC012E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3b384a0be81ffeb7f2faada5ab850b2cbc88996","datavalue":{"value":"For a partial commutation relation (a symmetric partial relation) \\(\\theta\\subseteq A\\times A\\), over an alphabet \\(A\\), we denote by \\(\\bar\\theta\\) its complement: for a string \\(w\\in A^*\\), denote by \\([w^*]\\) the set of all words in \\(A^*\\) equivalent to a power \\(w^ n\\) of \\(w\\) under the partial commutation \\(\\theta\\). This set is a regular language if and only if \\(\\bar\\theta\\) as a graph on the vertices \\(A\\) is connected [\\textit{R. Cori} and \\textit{D. Perrin}, RAIRO, Inf. Theor. Appl.19, 21-32 (1985; Zbl 0601.68055)]. The present paper investigates the starheight of languages of the form \\([w^*]\\) for \\(\\theta\\) as above with \\(\\bar\\theta\\) connected. It is proved that (1) when \\(\\theta\\) is not connected, then the starheight is one, but (2) when \\(\\theta\\) is connected, then the starheight can be arbitrarily large: for each \\(n>0\\) there exists \\(w\\in A^*\\) of length \\(O(n)\\) such that \\([w^*]\\) has the starheight equal to \\(n\\). This second result is a stronger form of a theorem (presented without a complete proof) by \\textit{C. Choffrut} and \\textit{C. Duboc} [Lect. Notes Comput. Sci. 267, 190-201 (1987; Zbl 0634.20026)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308983$214C0B83-480B-4A79-9A3B-43422532450E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308983$F9FB4556-0553-4593-8AF7-2E14213AD935","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308983$BB739016-08CE-429F-A5AA-9C0B682E4F4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d9d7fe04f058e55d43f42ab1851a51223d98c2c","datavalue":{"value":"465564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308983$FF146861-13C9-4F91-9A5A-924453EA1483","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48b241c2e53ac9c4073e4f6a37f6442b7c79d7d","datavalue":{"value":"free monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308983$DC190236-D61B-4386-8E6B-8FCBE954A11A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecfd805ad82096c60f326b3b4fc9b776ac9b8279","datavalue":{"value":"rational set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308983$C39C6F2D-8C00-4EFA-AA07-35F2D66C5203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26e5eca5994646fbb557c5c00b45e5609f5416bc","datavalue":{"value":"partial commutation relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308983$61AA7728-8858-4548-8E54-2F8140F2CD2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea9b35a533d874f0a32d77e584c8b61e0e7c2fe","datavalue":{"value":"regular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308983$769F1E01-CB9D-49F9-927F-68106B7A89AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d11561106578b256871905ca2322bd3e204eb9d","datavalue":{"value":"starheight of languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308983$39C6D062-C31A-4C52-8AF8-7B5F2938A645","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"42210bafdd52b4cbc4a62733feb51d89cc3d12b1","datavalue":{"value":{"entity-type":"item","numeric-id":224640,"id":"Q224640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1308983$8EE942C4-581E-4C44-AC30-DB701A4B67D5","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":"Q1308983$9BBB9ECF-C69B-48DE-A417-04BDBAC0EE98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f404263acac1c9ddd57f48a121469c7e4525a97","datavalue":{"value":"https://doi.org/10.1006/inco.1993.1049","type":"string"},"datatype":"url"},"type":"statement","id":"Q1308983$DE639987-C477-46FD-9501-87FD094F61CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9a39deee3f8e43f2d1c018cff3148cfeb32b5e18","datavalue":{"value":"W1990586430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308983$95C9F8FD-5461-4C96-945E-EF5FD1E61F7D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6e9a146e66830a6883583f3ddd3bc774c5d4b48e","datavalue":{"value":"10.1006/INCO.1993.1049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308983$B6F0304B-F1A5-4193-930A-8E335E0BD0EC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf94709a3a8ad1b830b34cfd9520d4aa1599ad78","datavalue":{"value":{"entity-type":"item","numeric-id":3772414,"id":"Q3772414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14c3e625d488a1264534a66ef6eb6cf610bb6976","datavalue":{"value":{"amount":"+0.9126967191696168","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":"Q1308983$47990B8F-65C2-4336-BB9B-F8F6F2350B77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19071b82661d6ab803426b2b2ba4b5b6015e4a2e","datavalue":{"value":{"entity-type":"item","numeric-id":1207944,"id":"Q1207944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cf78aba5c33959e282e6e89c52a4e7304519e53","datavalue":{"value":{"amount":"+0.7969292402267456","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":"Q1308983$70DBD4B1-D708-4A8B-8D9D-AE611B819523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"293df68d59dbb65d56e4836527160ad2dac2549b","datavalue":{"value":{"entity-type":"item","numeric-id":672729,"id":"Q672729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e914b331dd52e82b33bca30d2a9483b0bc1dbb7","datavalue":{"value":{"amount":"+0.7962417006492615","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":"Q1308983$5C6C71ED-40C6-4B1D-B9A0-6EC4CF2A5DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21dd92563383d93f87cf6e97229352579d94b081","datavalue":{"value":{"entity-type":"item","numeric-id":3723719,"id":"Q3723719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da8b1ff37da96563c0544dee03621a8764f6ec39","datavalue":{"value":{"amount":"+0.7952209115028381","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":"Q1308983$B7D9F74E-51B9-4B4F-9474-02EC37895748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c9dcabac82e310a82afd81221126cfe6c18214b","datavalue":{"value":{"entity-type":"item","numeric-id":4316609,"id":"Q4316609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e76d514d87438173998194b362bf4d86ad55011","datavalue":{"value":{"amount":"+0.7777155637741089","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":"Q1308983$0349DFF8-B276-4DA2-8688-5037431E3255","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the starheight of some rational subsets closed under partial commutations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_starheight_of_some_rational_subsets_closed_under_partial_commutations"}}}}}