{"entities":{"Q2893309":{"pageid":2904034,"ns":120,"title":"Item:Q2893309","lastrevid":42458846,"modified":"2025-06-28T03:58:41Z","type":"item","id":"Q2893309","labels":{"en":{"language":"en","value":"Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6048139"}},"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":"Q2893309$3B2F1BED-0F16-4917-85E4-7FE2B7B2280E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c5f61ce2ffab8528e2aa333931a60dd5d8e73840","datavalue":{"value":"1267.68136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893309$132665EA-EF88-4BF2-A250-4E976D9AF2FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"278c523e804e8886df2d4397085577532270faf0","datavalue":{"value":{"entity-type":"item","numeric-id":1941387,"id":"Q1941387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893309$6B84F368-FCC9-409B-A08E-4E8E68C32B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb8579d08d02888dcfc6c4a0d1e7ad3780689962","datavalue":{"value":{"entity-type":"item","numeric-id":284844,"id":"Q284844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893309$57AD0FA7-2679-476F-B307-AC819E1702E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a7e572a8e89f185fad728e7d88ff8c270f60d2c2","datavalue":{"value":{"entity-type":"item","numeric-id":785800,"id":"Q785800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893309$69068217-90EB-4C22-AF88-DD7637980263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"01e048c609c571a9032d2c0f19ccde9301c9fc1f","datavalue":{"value":{"entity-type":"item","numeric-id":236475,"id":"Q236475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893309$ED95A7E9-720B-41E3-BDB8-6FDD8AA356E6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f318557c66fd6d7ed4e56cf07066ee7032aec4a0","datavalue":{"value":{"time":"+2012-06-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":"Q2893309$2D7DA3C2-0885-4609-B311-02D8700E9620","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b754b5370fdec9fa2a90a5cfa0af057cd21d8e0a","datavalue":{"value":"http://iospress.metapress.com/content/n00875112353364l/fulltext.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2893309$82C48DF0-63C7-4038-8BE6-226C962306BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893309$5C0EDED2-51EA-491B-AF1C-1A6780697CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893309$DD6668AA-5D01-4670-84A0-0E95A9FB9E53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893309$518B62EC-D4B9-43D8-8F35-6BAD1C0E87D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03eb01fc2eae66c45ff58c211043fe61a29e076b","datavalue":{"value":"6048139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893309$AA8AF6B3-01AC-42C6-99E3-EC11A34C43AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d991512b4c19755eab079051727c7279e5cb3b1f","datavalue":{"value":"syntactic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893309$13804043-8501-48D4-B312-D8BA56CB55D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93d94f4ee67cb3900f482699adb24fe68e0747de","datavalue":{"value":"periodic set of integers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893309$B6B7358B-D690-4F8F-BE11-12DE2615A442","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":"Q2893309$9F5D9341-6B3C-43F9-9B4C-318F299F72D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57a44ac05288f4aa452f9a4f9445b8b03cbcc46e","datavalue":{"value":{"entity-type":"item","numeric-id":3004606,"id":"Q3004606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aafc9fee0918f9010f8f9a73cf357fc4191dcc1","datavalue":{"value":{"amount":"+0.8921802","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$A9720414-B7E8-4560-8AAA-3BB937965C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77059973e1c426656e4f35abca963384fb5042c2","datavalue":{"value":{"entity-type":"item","numeric-id":5111450,"id":"Q5111450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27bd6b4ba86e29ec3090cbbefd37e89aeffd518c","datavalue":{"value":{"amount":"+0.7519278","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$62B66DA6-715D-44E8-AC4F-7623F252F066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c3b23caf4295f5202fff2eaa492d016b6b772e2","datavalue":{"value":{"entity-type":"item","numeric-id":5227519,"id":"Q5227519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"026a89cef71f3ce476d09cfd7294dd2a90f86f84","datavalue":{"value":{"amount":"+0.7212832","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$A05A782B-165B-4A70-9690-1BFA7CC13436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42d6c84accb937e9d2621ce5730c12ce26ab0bb7","datavalue":{"value":{"entity-type":"item","numeric-id":5300854,"id":"Q5300854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b860fb5cde7b5351c21ce751a7e1db09f562cfb","datavalue":{"value":{"amount":"+0.69901806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$0965C3F8-90A7-45CA-B368-34EEB0A509CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"169b9e42abac65c8886b4075a5644c832be891a5","datavalue":{"value":{"entity-type":"item","numeric-id":844208,"id":"Q844208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7ccc324a2dd828e988a630a8730da20fd289f21","datavalue":{"value":{"amount":"+0.6811428","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$C645B593-D6C2-47C7-A473-7BB27B2038C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80d794ceff3997422ef31f81b0473e43c48d6aeb","datavalue":{"value":{"entity-type":"item","numeric-id":5075706,"id":"Q5075706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"773f4269c031961e92c11141a82a8c8745ed5444","datavalue":{"value":{"amount":"+0.65626067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$9B8C7A09-4A32-4F07-A3B2-37B00DA640EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9338d4db353adddb17bae27f138fa5c2ccc2a50","datavalue":{"value":{"entity-type":"item","numeric-id":1079381,"id":"Q1079381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d68e74f0cb0508ae449b08f5ffbc8c5383058d71","datavalue":{"value":{"amount":"+0.6533084","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$1D31DAF8-1112-441E-A6A4-DD43392E64CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61bf15db9a14c8f8ce5833dc07d25cee2c149844","datavalue":{"value":{"entity-type":"item","numeric-id":4650112,"id":"Q4650112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50fbbbc6e3c9db636e7913ab812f705695b1a8df","datavalue":{"value":{"amount":"+0.64482945","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$E8247FEF-1C8C-4E9D-9E5D-77E6516FD9C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b089d177a010fa8d62b9e291af961ad2e8d9870c","datavalue":{"value":{"entity-type":"item","numeric-id":3533010,"id":"Q3533010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5909b53e4fbf16831d92575446f401f5d24fffe5","datavalue":{"value":{"amount":"+0.64256513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2893309$F0C7663A-A988-4B0A-9E23-D0A264463560","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"211d4f235db70f5273c4a790efc2e4d3a94f97eb","datavalue":{"value":{"text":"Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2893309$77B0ECB5-8B5E-42CD-904E-3A4A8E0E8A7E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1529db038bde6a8aed76ac5e8432917aee1a9200","datavalue":{"value":{"entity-type":"item","numeric-id":2803574,"id":"Q2803574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893309$AFA191A3-2CAF-41B2-9897-3698C5B45A15","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"39db264b06cbde157de7e17ad9a68a6eea9dbde6","datavalue":{"value":"In this paper the authors investigate the syntactic complexity of the language \\(0^*\\mathrm{rep}_b(m\\mathbb{N})\\) formed by the expansion in base \\(b\\) of the multiples of the integer \\(m\\). An explicit formula for the syntactic complexity for such a language is provided in the following cases: for \\(m\\) and \\(b\\) being coprime, the authors also give the syntactic complexity of the language \\(0^*\\mathrm{rep}_b(X)\\) for a generic periodic set \\(X\\) of period \\(m\\), if \\(m\\) is a power of \\(b\\), and \\(m=b^{n}q\\) where \\(q,b\\) are coprime, \\(q\\geq 2\\), \\(n\\geq 1\\). Extending the result of \\textit{M. Rigo} and \\textit{\u00c9. Vandomme} [Lect. Notes Comput. Sci. 6638, 477--488 (2011; Zbl 1330.68178)], the authors give a lower bound for the syntactic complexity of any ultimately periodic set of integers written in base \\(b\\) and period \\(m=db^nq\\), where \\(q\\) and \\(b\\) are coprime, and the set of prime factors of \\(d\\) is a subset of the one of \\(b\\). Finally the obtained results are applied to the decision problem of checking whether or not a \\(b\\)-recognizable set of integers is ultimately periodic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893309$5A190D16-A319-49F9-ADAE-0495C507883C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"45156d9276118c353d703acf608821bd8f325600","datavalue":{"value":{"entity-type":"item","numeric-id":305763,"id":"Q305763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893309$772948B2-1D7C-482B-A4CF-6C88E216331C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2893309","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2893309"}}}}}