{"entities":{"Q418146":{"pageid":419913,"ns":120,"title":"Item:Q418146","lastrevid":61693581,"modified":"2026-04-11T01:01:11Z","type":"item","id":"Q418146","labels":{"en":{"language":"en","value":"On the expressive power of univariate equations over sets of natural numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6038296"}},"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":"Q418146$EB825BB9-55AD-4831-A08A-F8FB295E61D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"207e404cd20a1eaa2d92e1f0a0f56a5ec58c956d","datavalue":{"value":{"text":"On the expressive power of univariate equations over sets of natural numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q418146$DF79535A-3595-45B8-AE11-46FDFFA44F42","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af1a5d1b2e295171d366a49d11c637c898a95802","datavalue":{"value":"1263.68102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418146$686EA481-72BB-402E-9D0B-4C6A77107BE7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"396be6cf4077d85b5a940d5425abf76338b8a241","datavalue":{"value":{"entity-type":"item","numeric-id":248926,"id":"Q248926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$F33388B6-A44F-41D4-8050-AF6A14A8E02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b32136b1c003e49ded6a8ec406aedc9cb1ab5742","datavalue":{"value":{"entity-type":"item","numeric-id":6769145,"id":"Q6769145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$26CD27F7-77CD-4E8D-9EDA-C313841BF5D7","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":"Q418146$B1A21AD2-B03A-4ECD-BC0C-007E962CCD2A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4dd357d987d60d499edfc98e682fe931160623b6","datavalue":{"value":{"time":"+2012-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q418146$7CB909B8-3EBF-49D9-9C0B-534D26943E85","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c6da54a7bbc54737925e3fd67beb9d97ad2e674","datavalue":{"value":"This paper deals with one-variable equations of the form \\(X=\\varphi(X)\\) over sets of natural numbers, where \\(\\varphi(X)\\) is an expression, which may contain the operations of elementwise addition, union and intersection, as well as ultimately periodic constants. Such equations of a special form, where \\(\\varphi(X)\\) is a union of intersections of sums of copies of \\(X\\) and singleton constants, correspond to one-nonterminal conjunctive grammars over a one-letter alphabet. By encoding the example of a non-regular unary conjunctive language due to \\textit{A.~Je\u017c} [Int.\\ J.\\ Found.\\ Comput.\\ Sci.\\ 19, No.\\ 3, 597--615 (2008; Zbl 1155.68040)] into a unique solution of a one-variable equation, it is proved that sets of natural numbers generated by one-nonterminal conjunctive grammars need not be ultimately periodic and can have exponential growth rate. On the other hand, it is shown that a set of natural numbers cannot be obtained as the least solution of any equation \\(X=\\varphi(X)\\), if the ratio between two consecutive elements of this set is not bounded (this covers, in particular, super-exponentially growing sets). This implies that one-nonterminal conjunctive grammars are less powerful than general conjunctive grammars. Further, it is proved that sets \\(S\\), for which \\(S + S\\) is co-finite, (in particular, dense sets) can be represented by one-nonterminal conjunctive grammars only if they are ultimately periodic. Finally, using a density argument, the set of all odd primes is also proved non-representable by one-nonterminal conjunctive grammars. These are the first results on non-representability of sets of low computational complexity by equations with union, intersection and addition.","type":"string"},"datatype":"string"},"type":"statement","id":"Q418146$CEF66313-496F-4DA3-B7A8-200358AA2899","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e360e835094103aee0817dd4cb43ec4ae2adb196","datavalue":{"value":{"entity-type":"item","numeric-id":443745,"id":"Q443745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$8A2DA484-57EC-4914-B2B8-44F0FB4DBAF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418146$97B4AE30-C674-4D99-AF68-A8AEC43C805C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418146$1DF3A907-D6EB-41AB-A7EE-231ED9A51D91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fa980576713ca1132b0ccd24428d99299e52d8c3","datavalue":{"value":"6038296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418146$35E3DDC5-9C8E-48ED-8A4B-D72A5E3A64D9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f84130e4e0b118e079e2ddfa9fcd7438369f6cff","datavalue":{"value":"sets of natural numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q418146$B0F8607B-D3E5-42CE-B5D7-F67F117771AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0666c4bc6d7a9869d42536816396636b9a36eaa","datavalue":{"value":"language equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q418146$AD86B008-AB5C-4CB5-B141-E34D7A235E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b00d6a3a9da75d87082861f20b9cea223adf9ce0","datavalue":{"value":"conjunctive grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q418146$EFF022D8-F0C4-4665-9CD7-4FF1FDD2F4F7","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":"Q418146$8375FA48-1E57-4925-AFC8-9DF251FDAB5E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"05fada74c662e7350d3db9a77a1a2d9dd061ff3a","datavalue":{"value":"https://doi.org/10.1016/j.ic.2012.01.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q418146$9834754E-BDB7-4713-B439-32F6BDA728BE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"da578aac6a3d4e1402c852f4bf2aee68aedc6bd0","datavalue":{"value":"W2022226854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418146$840ABA5B-2357-422F-B5FA-3E995D56466C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5237f78a003fe7b4a929c7746842033e5266577c","datavalue":{"value":{"entity-type":"item","numeric-id":5747087,"id":"Q5747087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$04DC49AE-5868-4EC9-A04D-1CA513DB3375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6522af7581ff424a217136016f62495c14f0c524","datavalue":{"value":{"entity-type":"item","numeric-id":1847139,"id":"Q1847139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$B4101341-3C5C-4DC2-A937-3A37D385FCFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee5723528e4b7b9738b0b3bbaf040f1adce342e7","datavalue":{"value":{"entity-type":"item","numeric-id":3575156,"id":"Q3575156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$8EAC45A8-E252-4B9C-AF8A-7ABA9057F9B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4869c144f6db90de91d60ef67f1bb3ee0e132ebb","datavalue":{"value":{"entity-type":"item","numeric-id":3538852,"id":"Q3538852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$04573C77-A429-4658-ACFA-DEFA3B755936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af636d3150526ff3aa6cb7dd6688270fc780c18","datavalue":{"value":{"entity-type":"item","numeric-id":2268341,"id":"Q2268341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$AC04E780-89B4-463C-9743-F5DFD9C5EC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dd9ad93c4def99bc91ce8d87f9ad3b0d324dd7f","datavalue":{"value":{"entity-type":"item","numeric-id":3520304,"id":"Q3520304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$B71338AA-7830-48A8-B179-D2DCFD416ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"272776f2e3c205196dfaf4b5956e2c5b760aaee9","datavalue":{"value":{"entity-type":"item","numeric-id":2643146,"id":"Q2643146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$07DC9364-43DA-4344-829E-5529FA5578F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0a6137af977465917fd440f4ca36b83c8de18cc","datavalue":{"value":{"entity-type":"item","numeric-id":1334656,"id":"Q1334656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$1CAB1105-0AD7-494B-B893-3D85124E68D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aad262fc4276500ee1045779ffdc072e992800e","datavalue":{"value":{"entity-type":"item","numeric-id":4056099,"id":"Q4056099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$335298CF-6849-4F64-A883-0602FC74FB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f807077b4188e4441802ee77fc5ab7dd646da108","datavalue":{"value":{"entity-type":"item","numeric-id":3309910,"id":"Q3309910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$EFB370DD-76D4-4C5B-B780-54D861DFF997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a1b938450b5e3c1226aedb2b85438c3d6872640","datavalue":{"value":{"entity-type":"item","numeric-id":4889853,"id":"Q4889853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$743D1F1E-B6C9-4B88-B830-4A73ECC51703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f4bb2f9cda641a8703f1fa0b2c773f3ecfe6b7","datavalue":{"value":{"entity-type":"item","numeric-id":4531380,"id":"Q4531380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$B51F7D22-0C55-49B7-88B6-AAC918354B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58421e016875d9c364bcf6e2e6b06a895133a7f9","datavalue":{"value":{"entity-type":"item","numeric-id":596108,"id":"Q596108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$61CE3FC9-03C6-44C5-91EC-66CD7DD9B594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef5d664317daa70e1effcee3ab0f27d96033b1df","datavalue":{"value":{"entity-type":"item","numeric-id":972384,"id":"Q972384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$BF755675-8B0E-4E8B-89E5-DD6544DC85BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c3e71fbd5ad582e94786df5ac2c307fc566bae4","datavalue":{"value":{"entity-type":"item","numeric-id":714852,"id":"Q714852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$9626D36A-F3AD-4009-A10A-4AFA3394A0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"079bb89ce913d6b959502bf31254af4059df4800","datavalue":{"value":{"entity-type":"item","numeric-id":880178,"id":"Q880178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$54422EF3-E0C4-49BB-9618-B061C8E04D15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cec97d9549214efeae9ef9fad9743ea4b569210","datavalue":{"value":{"entity-type":"item","numeric-id":764318,"id":"Q764318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$B37D45C1-E9FB-4231-AC39-322030A41676","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b476279f9ef74fddb27272ad70ec34f0a4ec2a74","datavalue":{"value":{"entity-type":"item","numeric-id":5625141,"id":"Q5625141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q418146$97718C33-6ED5-41BD-AA48-CD165C51ACF3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"91970ae7d1f9d2ba700044f1dc929bb77f08a727","datavalue":{"value":"10.1016/J.IC.2012.01.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q418146$09F95454-20EC-496A-9207-E8016687B742","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5390281b76ea772e157c5c117dd56c175c22f331","datavalue":{"value":{"entity-type":"item","numeric-id":4913002,"id":"Q4913002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af0e266b49c72ab5d7ce35ba39d293176e1d1250","datavalue":{"value":{"amount":"+0.8580642938613892","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":"Q418146$C0D3E395-5B28-46C6-9A72-9CC9CE09A7EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84b4fbfe01a2c9bfbdcc233dfb2df045ec0d6012","datavalue":{"value":{"entity-type":"item","numeric-id":3005912,"id":"Q3005912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b7733eddb4e83d6136fe1ec14785c2cf469343c","datavalue":{"value":{"amount":"+0.8315838575363159","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":"Q418146$7A32D9D8-43C0-4F61-90B0-283E4F12482C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"769783957db072e940243f62c90c91731e057a4e","datavalue":{"value":{"entity-type":"item","numeric-id":5390009,"id":"Q5390009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"956be47f4f569ee0fd533d67b3a10f60226d1465","datavalue":{"value":{"amount":"+0.8219922184944153","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":"Q418146$9A2DFC4B-01AD-49E5-8C5E-E68747687AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaa303d33046acf85b9c473bd0e736dcceac1177","datavalue":{"value":{"entity-type":"item","numeric-id":3113773,"id":"Q3113773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"621adf99ecc82213c42e79829fc4a439dfbfe030","datavalue":{"value":{"amount":"+0.7882154583930969","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":"Q418146$3FEF7D7E-F387-4992-9DA8-EC9C7927C6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad23c46af0afa8a28606d05b57d94fd0e37d262b","datavalue":{"value":{"entity-type":"item","numeric-id":3086245,"id":"Q3086245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d3c04ca28367278d8765637fa1f1eae648d60fe","datavalue":{"value":{"amount":"+0.7819775938987732","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":"Q418146$7478A06E-C7DB-491D-AD11-44D1D6BC5E7A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the expressive power of univariate equations over sets of natural numbers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_expressive_power_of_univariate_equations_over_sets_of_natural_numbers"}}}}}