{"entities":{"Q1065555":{"pageid":1076307,"ns":120,"title":"Item:Q1065555","lastrevid":66189624,"modified":"2026-04-12T08:09:28Z","type":"item","id":"Q1065555","labels":{"en":{"language":"en","value":"A note on Parikh maps, abstract languages, and decision problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3924160"}},"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":"Q1065555$F1985DE7-CA06-435A-95E8-BB621956F7C7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12897c571bfced60d64af7e1cfd7eec0d7a527dc","datavalue":{"value":{"text":"A note on Parikh maps, abstract languages, and decision problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1065555$84C5FA40-2A51-43F6-A214-9D6AF46FAA3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d1941e294828726f0bf7c5f9e1eb167bca4f57f3","datavalue":{"value":"0577.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$7511DC44-0FBF-46C8-99E5-CAAEA3C50011","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7237d132aae52834a80576e657e558ae8655d002","datavalue":{"value":"10.1016/0020-0255(85)90047-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$DA2D169C-965B-407B-8806-77D77B1355C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec87823d605add929983907eaf356268b6db6999","datavalue":{"value":{"entity-type":"item","numeric-id":1065554,"id":"Q1065554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$8EF6315F-BB9B-428A-87B8-B85B214959B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fbe9a2f35bfbb97131fdd4f5f88a8af0c602f0","datavalue":{"value":{"entity-type":"item","numeric-id":688713,"id":"Q688713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$6B2D247F-A980-4972-A1DF-72482C5C6D0D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$414F24FD-F3D9-49EF-8E3C-53D672EFC46E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1065555$CDD2D618-59D3-4657-9C72-2F64A4C7316B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e670cc36d946c60f8c399140091906a43f3a35ad","datavalue":{"value":"We consider formulas similar to Presburger formulas, but extended by allowing the predicate \\(|\\) (for divides), but not allowing universal quantification of the resulting expressions. The solution sets for such formulas are known to be not semilinear, in general. We show that some results concerning decidability questions for classes of languages with effectively constructible semilinear Parikh maps can be extended to languages whose effectively constructible Parikh maps are solutions to these new formulas, which we call ''modular''. We suggest that modularity may offer a natural extension of semilinearity, in which many previously established results may remain valid.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065555$D7D2EF97-5B19-43D2-87EE-61D58955E01D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$9528822D-61EA-400F-A913-A8224FDCECF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$D9CFC3A8-0CED-4B85-9F41-A942080CB31D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$F5DC164F-EA3E-4A63-BF3B-FC71B774269F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"756e54063cbb643f5f13cc1469766d4c7c8f5a55","datavalue":{"value":"3924160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$4C3295A9-9C5E-41AA-8A42-958E0438575B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36684c3e7ff30f81e4698e5d7b5f91b220a88e16","datavalue":{"value":"semilinear sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065555$975D6E2A-B6C1-4873-969D-046BCEA0B5A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"335361f2d5472f7ca846e53db25ccb4027120f89","datavalue":{"value":"division","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065555$45933C64-9D40-483F-B4A6-59ABCF7BDB02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"516366c820bb8f9a6d4de2d0a32665e702250894","datavalue":{"value":"Presburger formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065555$9D4B50BF-44A4-4F50-B6CD-BD0B015E2ED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065555$1E5C41A6-9959-43C2-AF77-7F28B94BFA5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1510776740c35361175d9feaca5986396234b04","datavalue":{"value":"Parikh maps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065555$7AB3426A-B7D0-4413-B011-4F58319956F1","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c007ae1867363f659c11dfe2e26b294ddb7e58e3","datavalue":{"value":{"entity-type":"item","numeric-id":33608,"id":"Q33608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$12492DD9-5B15-491B-9293-A96F0906980D","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":"Q1065555$AFAC5703-4C3F-4956-A140-A01F3DF756BD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0470b69f33a2fe4e92d74c83bd721fd861413650","datavalue":{"value":"https://doi.org/10.1016/0020-0255(85)90047-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1065555$29F8E46C-EF0B-4242-84EE-A9A3C3B8D7CC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8bca89d36c8b2ef4aec063c7a832adb02dd9184a","datavalue":{"value":"W2006830748","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065555$7292873A-84D3-4D46-8481-9940069506F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6cc3c6c9b42b892eb81ef88247f7b0dd9090670","datavalue":{"value":{"entity-type":"item","numeric-id":1065555,"id":"Q1065555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$56E0E895-4B70-4F56-AEE8-42DBE7619D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e97002deaa32bce9238411fd6668f6b28c627864","datavalue":{"value":{"entity-type":"item","numeric-id":5536272,"id":"Q5536272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$674645DF-B4E2-4032-A3E3-E8B496D46B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"870c5a38858355caeeae9f446f0a3e85a9be75a4","datavalue":{"value":{"entity-type":"item","numeric-id":5517673,"id":"Q5517673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$8E38F97F-9DD8-4D5D-AB4E-338CB5472A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8589e0d1a6999e28c7f5ecb6dae5bccb4b909f36","datavalue":{"value":{"entity-type":"item","numeric-id":1242687,"id":"Q1242687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$59170553-B37A-473F-A44F-DFE299AC7294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b16bcbc18fd74a19ac9a32b503ccd2e7113abd46","datavalue":{"value":{"entity-type":"item","numeric-id":3960829,"id":"Q3960829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$E6776EC7-913E-4E73-AB1D-F15CFD3DFB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4350892d7df19387ec0804bd15d8a9dc062b47c","datavalue":{"value":{"entity-type":"item","numeric-id":1151753,"id":"Q1151753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$E396B016-1464-4D82-A280-D39B1E1906C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"522b2a12012b04970578e80003874032a766bbde","datavalue":{"value":{"entity-type":"item","numeric-id":3680282,"id":"Q3680282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$639AA383-5CF0-4609-9F90-F68B83C9394B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$E9BC4BCA-55B3-4F86-BDB3-CB0D384FEB69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91da9d59678264115e058363c71ebd91f6c4697a","datavalue":{"value":{"entity-type":"item","numeric-id":1164438,"id":"Q1164438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$E4D4B1FB-7B95-4B21-A44D-B20D83C584F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82c623f3446812c39e5ac3592eb9bf23663f505","datavalue":{"value":{"entity-type":"item","numeric-id":5561967,"id":"Q5561967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$EA4DB2E8-C2BE-4648-8B7C-5322D9A74572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182981e0e770b39d22d2da0fccd0d6dd8798182f","datavalue":{"value":{"entity-type":"item","numeric-id":4140393,"id":"Q4140393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$4E97008A-2B15-4D37-B263-CE504DE36D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c450965700884520792d78d9cf9b8d54507d87","datavalue":{"value":{"entity-type":"item","numeric-id":5626293,"id":"Q5626293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$8724D40D-7F94-442F-8E36-C6F4E6265B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4213ac9da6566bb3d1d8a6c0670bd01a09e0e7d","datavalue":{"value":{"entity-type":"item","numeric-id":1394126,"id":"Q1394126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$5625D629-D646-42F0-BAD6-F5A755B16360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35fe67728decfb74b0425f1c8c7de107bb903c68","datavalue":{"value":{"entity-type":"item","numeric-id":2544411,"id":"Q2544411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$38873B2A-9BE3-44BF-8459-CD2747EB88EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2edfe8015b58c579c54c78cbe4fe122a242df00f","datavalue":{"value":{"entity-type":"item","numeric-id":4152529,"id":"Q4152529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$EDD5C039-7FC7-4EF3-B407-85DFA3D84C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d46d53aaa78e4e1f3286eef514e163c5ea4ffb6","datavalue":{"value":{"entity-type":"item","numeric-id":5534924,"id":"Q5534924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$9E05FB54-2AEB-40EB-B826-7D5094DA1E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8107b480decc678c92b78dee11f4a9915c90692b","datavalue":{"value":{"entity-type":"item","numeric-id":5541339,"id":"Q5541339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$5CEFCEA8-AA2F-4B99-B509-7D5E49AD9B33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6e8c071721159cc60ac17decd03c2a83d512eef","datavalue":{"value":{"entity-type":"item","numeric-id":2555753,"id":"Q2555753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$3C610DBC-2216-404E-AD0C-21AA44FEF960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73ea1a986b8212f90121d21e0a14bb9807498264","datavalue":{"value":{"entity-type":"item","numeric-id":5791204,"id":"Q5791204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$763A0BA4-CA4A-4C52-AF24-FFE5CA89D1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e3a8c411e782df3d5f847a6156dfacf11e8b4b","datavalue":{"value":{"entity-type":"item","numeric-id":5573388,"id":"Q5573388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$EBC7D109-CFF5-4A97-9437-D2C5D9550958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d169efcbdd04d1e16f6b81f3f41571dfa1a0fcf5","datavalue":{"value":{"entity-type":"item","numeric-id":2550634,"id":"Q2550634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$D15F47D9-2738-419A-BCDF-EB5C192FECCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1613a6ff5ac7b010de5ba58e55ebd9cdec3d5273","datavalue":{"value":{"entity-type":"item","numeric-id":5765445,"id":"Q5765445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065555$4646ED66-B021-4769-AF14-549E3B6E914D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d7fd02908e7a9276889b8098056702d033eb5f9","datavalue":{"value":{"entity-type":"item","numeric-id":4712759,"id":"Q4712759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2698eecf085a172db54820ea7a3bb8540d1ba646","datavalue":{"value":{"amount":"+0.7074339389801025","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":"Q1065555$A413900B-6CF2-42CD-8FA8-006A9FBF9F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f1447835d6e401b9895906f45c2acbcd9285833","datavalue":{"value":{"entity-type":"item","numeric-id":2708967,"id":"Q2708967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e932359de84d0f3d1a84e39e4f0ba3281891ef1","datavalue":{"value":{"amount":"+0.7038209438323975","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":"Q1065555$F1E04A07-35CD-4174-B9FA-AFFCC2C24454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67f7b7805a8cefbf4c6bbda08ce3cda4619cbd1f","datavalue":{"value":{"entity-type":"item","numeric-id":674912,"id":"Q674912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9acda27fd1440c63be6e27106040856b51781dc","datavalue":{"value":{"amount":"+0.7032667398452759","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":"Q1065555$D93B2750-2B6E-4BE7-A2CF-29878EBBC40B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"501c2309ff43e0eeff74a21936fcb0099f729925","datavalue":{"value":{"entity-type":"item","numeric-id":5404899,"id":"Q5404899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e115784b7b1884ea243dd8273ccfd34858ce29d5","datavalue":{"value":{"amount":"+0.6995273232460022","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":"Q1065555$C5AD4BB1-CA22-46EE-805B-7B44E2EC7A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fd35b6facc7afb93eabfe3333ae042a8205eb7f","datavalue":{"value":{"entity-type":"item","numeric-id":4535049,"id":"Q4535049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f16acec962547c5180d395393bbe4aec454b2de3","datavalue":{"value":{"amount":"+0.6982988715171814","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":"Q1065555$3A0607C8-9F6C-47F2-9E35-89576B0AB89B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on Parikh maps, abstract languages, and decision problems","badges":[]}}}}}