{"entities":{"Q2354594":{"pageid":2365337,"ns":120,"title":"Item:Q2354594","lastrevid":52308425,"modified":"2026-01-21T10:03:17Z","type":"item","id":"Q2354594","labels":{"en":{"language":"en","value":"Omega-rational expressions with bounded synchronization delay"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6460121"}},"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":"Q2354594$B3D87128-B655-41F2-8041-9BA160214245","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7aeba11181cc11c9fd262e49f9e2ce9123fd8255","datavalue":{"value":{"text":"Omega-rational expressions with bounded synchronization delay","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2354594$F2293317-8282-49E9-A255-14A39EBD156B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc5700d171857f3c85df74fbfe3e556b22650923","datavalue":{"value":"1343.68135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354594$0C400A13-D026-4A6B-8949-8BF6855C4C93","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"81c83c28843efefafe1f80734e19c2e6ff309a9c","datavalue":{"value":{"entity-type":"item","numeric-id":213104,"id":"Q213104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$47EB0636-95C8-4117-9BEF-3C058802D349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee0de4af1b7c20aa534acd2585628b6cd288f3b0","datavalue":{"value":{"entity-type":"item","numeric-id":263827,"id":"Q263827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$B77B1A27-444B-4155-87BA-41798048367A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$864B5F7F-D954-4612-94DB-E0A1ADDA3837","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fe3e643f8d0207e39cd4b06cb03fa62df3f53d7c","datavalue":{"value":{"time":"+2015-07-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2354594$0E18A6DE-91CF-456F-B740-64FDBB6F8920","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7d55e3345436940ec5d85dfd3d23e12a6d01923","datavalue":{"value":"https://dspace.lboro.ac.uk/2134/31969","type":"string"},"datatype":"url"},"type":"statement","id":"Q2354594$D181597F-263C-4F47-B0D4-FC8CB264106E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"730b22de37f080b2ff54e11407b6a29e14ca0d16","datavalue":{"value":"In 1965, Sch\u00fctzenberger published his celebrated result that the class of all star-free languages SF and all aperiodic languages AP coincide over finite words, i.e. \\(\\mathrm{SF}=\\mathrm{AP}\\). Perrin generalized the equality \\(\\mathrm{SF}=\\mathrm{AP}\\) to infinite words in [\\textit{D. Perrin}, Lect. Notes Comput. Sci. 176, 134--148 (1984; Zbl 0577.68076)]. As noted by the authors of the present paper, ``In 1973 Sch\u00fctzenberger presented another characterization of aperiodic languages in terms of rational expressions where the use of the star operation is restricted to prefix codes with bounded synchronization delay and no complementation is used.'' The authors denote this class of languages by SD.   Let \\(A\\) be a finite alphabet and \\(A^*\\) (resp. \\(A^{\\omega}\\)) denote the set of finite (resp. infinite) words over \\(A.\\) A language \\(K\\subseteq A^*\\) is called \\textit{prefix-free} or a \\textit{prefix code} if \\(u,uv\\in K\\) implies \\(u=uv.\\) A prefix code \\(K\\) has \\textit{bounded synchronization delay} if for some natural number \\(d\\) and for all \\(u,v,w\\in A^*\\) we have: if \\(uvw\\in K^*\\) and \\(v\\in K^d,\\) then \\(uv\\in K^*.\\) The authors note at the end of their introduction that ``We see three contributions in this paper: (1) We considerably simplify the classical proof \\(\\mathrm{SD}=\\mathrm{AP}\\) by using the algebraic tool of a local divisor [\\dots] (2) We easily extend \\(\\mathrm{SD}=\\mathrm{AP}\\) to infinite words by the very same proof technique. (3) We establish that \\(\\mathrm{SF}=\\mathrm{AP}\\) is an immediate consequence of \\(\\mathrm{SD}=\\mathrm{AP}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354594$0E4A2B79-76C0-4753-A5AE-544DF4360246","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354594$BB960891-02F3-4A79-8732-A2BBC76F4769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354594$3A113FCE-3731-40C6-A8FC-CA321A570D59","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e2bfedc07f39cf73f77ce158b8269dd803e706e4","datavalue":{"value":"6460121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354594$1D495C52-80DC-4185-9D5D-B492C5C0A08B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85f7180cee0cfd1e2e987b547fdcb99cc38e1dea","datavalue":{"value":"omega-regular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354594$65CFFB28-4136-48A6-B580-7F8775117001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53bdfb6af04f8c9f5906a0ff7ad737be573370f4","datavalue":{"value":"star-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354594$BA22D172-86DD-4FFA-8F8C-D59AF9D50AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013ea0ae18b29892b5726356388c7d5d42063956","datavalue":{"value":"finite monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354594$A0083E41-A199-49CD-8BF4-405739A142B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cddc269d881f08df8cb70e6947fca27900b9fab1","datavalue":{"value":"local divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354594$BAF52114-5AB4-45DC-A04C-8F6AE857C542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80dc582fd8231d6ffe6c4669e65cac0991d6d0a5","datavalue":{"value":"bounded synchronization delay","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354594$501E33E9-EAF5-41C7-B3BE-662BF509ACC4","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":"Q2354594$D1A320E0-0588-4BE4-9A3D-DCB70AC2821F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f5dffe351de4a67d34aaf4ebb1f3130ef0c96922","datavalue":{"value":"W2044927444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354594$872B67CA-97F2-4991-8044-6718C03867B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f809b829ad226aaf187e107ba4f2f8abde5cfa","datavalue":{"value":{"entity-type":"item","numeric-id":1066675,"id":"Q1066675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$BE99B43B-F238-44DA-A060-45094BEE3834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5be2cfdc456062ac293d666a4fb2ca8a6ad452","datavalue":{"value":{"entity-type":"item","numeric-id":859824,"id":"Q859824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$51337438-96AF-46A1-BD05-D9EB6A076CEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"847bdb99cb33a5f1424e34bd2acf52aa81768716","datavalue":{"value":{"entity-type":"item","numeric-id":3086925,"id":"Q3086925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$D73223F4-E1E1-4765-916C-483CCBF1C5A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0224cc11e92917094ceee66bf62982a9eb25550a","datavalue":{"value":{"entity-type":"item","numeric-id":3538848,"id":"Q3538848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$CD6E4379-507E-438C-89CB-B5EBCC92EA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82b996c64db99670728b3943ae82699501f73902","datavalue":{"value":{"entity-type":"item","numeric-id":2893300,"id":"Q2893300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$6AA9A651-3409-4912-86BD-AE25404792A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ed9ec9189b448ff02159be1a2ba930cf74a5cba","datavalue":{"value":{"entity-type":"item","numeric-id":5601239,"id":"Q5601239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$983C260B-2AA2-4722-86E5-317F60A57F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2dd225cb7a1f1b5d01838e5961bac1df864370d","datavalue":{"value":{"entity-type":"item","numeric-id":5641083,"id":"Q5641083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$9337C755-9BC2-4455-99B1-B027A3BBA877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dbe1a18e49eafc4e48a075e8a30b7a9bb67ee8a","datavalue":{"value":{"entity-type":"item","numeric-id":2557762,"id":"Q2557762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$62D77682-C385-462F-ACA1-8A07D0F3500D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcad196cde92ff58f605cb0c7899249dd4df74ca","datavalue":{"value":{"entity-type":"item","numeric-id":5317419,"id":"Q5317419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$19B63EFA-8C87-49C2-9F3E-246F8A774C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed68160731cf55d219ba94647825683328472c30","datavalue":{"value":{"entity-type":"item","numeric-id":3769981,"id":"Q3769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$0EF7B8B4-EAD6-4C30-A4B2-9CF635D03E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0a4208ba2661cb2d95de9176dc4be8560ac8a3d","datavalue":{"value":{"entity-type":"item","numeric-id":1103056,"id":"Q1103056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$2CD40A21-0AAA-4BFC-81FB-EC5B83BFBF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98554b277242125c67fbb359aa4c54ca22c25d4c","datavalue":{"value":{"entity-type":"item","numeric-id":5339335,"id":"Q5339335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$95B6C46F-33E0-4CA4-94E5-1511476EB057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc78875584d36fb0ed2343031d6517b47dd05d8","datavalue":{"value":{"entity-type":"item","numeric-id":4132760,"id":"Q4132760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$1A64972E-709B-438F-8A68-CAE0B7439E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6a75e85707c1f24d3c13217ffc94cef40ecf304","datavalue":{"value":{"entity-type":"item","numeric-id":1244582,"id":"Q1244582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$B5C79889-B9B6-48B4-8D9D-BE69163B2CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"337efcaa3ae20f38fff20af4d53f2602d2e9e5c4","datavalue":{"value":{"entity-type":"item","numeric-id":4407441,"id":"Q4407441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354594$B4744C5C-8E2A-4E20-8D3B-6090922CC0CD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ed55215571baa33443750addc99a49c3d8b7b604","datavalue":{"value":"10.1007/S00224-013-9526-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354594$B4090A72-8136-4856-9996-7088D505DCC5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21e5a98eba46126cf02df72911eb96ea9ac6deda","datavalue":{"value":{"entity-type":"item","numeric-id":2907490,"id":"Q2907490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edb8f9ae1d689e6ff25f235ce2c99f0ae45d80e2","datavalue":{"value":{"amount":"+0.9797443747520448","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":"Q2354594$6892FD69-191E-4AC4-BE37-D0BA880DB1A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbd3f4dc65a1a095e7b122936256225ea22a50fb","datavalue":{"value":{"entity-type":"item","numeric-id":4598271,"id":"Q4598271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87489b359903f107caea0d31151fc5b8b029663d","datavalue":{"value":{"amount":"+0.741994321346283","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":"Q2354594$F1D76ED5-E46D-4A82-AC94-C200F6CA1D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cd1cff9f96fff406310a106fb71beaa2d2dbff7","datavalue":{"value":{"entity-type":"item","numeric-id":4227133,"id":"Q4227133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dab605101d4b66e622b0600d99239a385765d14","datavalue":{"value":{"amount":"+0.7394365072250366","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":"Q2354594$EE4DB00D-FE3A-462E-9A94-A100527C09F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7560d1ef8b09046e9410e420e3bac11e9a335ce","datavalue":{"value":{"entity-type":"item","numeric-id":685453,"id":"Q685453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cbfeb327d8c6f50ca1f8f492a8419d856975fe9","datavalue":{"value":{"amount":"+0.735735297203064","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":"Q2354594$E9B598A3-7356-43D1-837E-EB768BB0D409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0cb61abe4105ddb9e1f87470e7e494f74878027","datavalue":{"value":{"entity-type":"item","numeric-id":4588867,"id":"Q4588867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f47e8b9b942ae98eb4cfacb93fdd71a84b66a7e6","datavalue":{"value":{"amount":"+0.735679030418396","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":"Q2354594$0D5734CD-D89F-4B10-B346-DFC2D4497FD4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2354594","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2354594"}}}}}