{"entities":{"Q794440":{"pageid":796288,"ns":120,"title":"Item:Q794440","lastrevid":64387815,"modified":"2026-04-11T19:31:17Z","type":"item","id":"Q794440","labels":{"en":{"language":"en","value":"On context-free and Szilard languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3860413"}},"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":"Q794440$960DC2E9-2810-47FA-9BE1-37F81E42397B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"96e598c89ba966cfcf50f1dc44f9d588f770a06a","datavalue":{"value":{"text":"On context-free and Szilard languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794440$63CDC4E3-9EEE-45EA-A9D3-1776C3E9375D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f40f16bb1c4b34cd5b7ac9baf28b0b0dc744e30f","datavalue":{"value":"0541.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794440$D18945BB-5991-44FF-B1CB-9043925858FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1574670ecf695b37718858d3d227b25aeac8ad04","datavalue":{"value":"10.1007/BF01937483","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794440$F1256611-3509-4885-9326-BA651AE39C61","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$D79F4B55-F7E9-4116-A17D-C8169CE62485","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q794440$DA5C2517-B060-4E45-B3F7-723A6CEA9F43","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe87104b8b488c05c82cd6537dcd944dc83ff01e","datavalue":{"value":"The Szilard language of a context-free grammar is context-free if and only if the grammar is ''half-bounded'', i.e. if there is a natural number k such that each sentential form contains at most k occurrences of all but possibly one nonterminal. However, it is quite natural to expect that also non-context-free Szilard languages of context-free grammars share some properties characteristic to context-free languages. The purpose of this paper is to study to what extent certain characterizations for context-free languages are applicable to non-context-free Szilard languages. It is shown that any non-context-free Szilard language does not have the classical pumping property of context-free languages (i.e. any such language does not satisfy the Bar-Hillel's lemma), but instead, the so-called generalized pumping is typical for Szilard languages. Moreover, it is shown that Sokolowski's criterion and Parikh's semilinearity theorem cannot distinguish between context-free and Szilard languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$88E6DCC6-7B05-4359-9B8F-EC95E61965F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794440$AFFD6878-5EE2-4A37-A8BA-33AFE29C5AE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18d4e66086a84c97853d3735a8ee5558907196b7","datavalue":{"value":"3860413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794440$718AC3D2-D7CF-4575-BB41-7BB23CCEA5DF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d26a8342ca7d60151602260681f35a580432e43","datavalue":{"value":"Parikh mapping","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$01C5BAE0-3763-4C0F-B432-156D5E2F2D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c75e0c066a8c026a2e933911ad84349d5aa03480","datavalue":{"value":"Szilard language","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$D1EF3E99-79F7-4244-B690-70AABB51529A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d8f95104569681b12147407e1fc63bde7079389","datavalue":{"value":"context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$5D727850-016A-4214-A4F8-A5F94988F89D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$D0DB1E09-8F85-49F2-A031-B52D082FB4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31e0018f25a733cafd65beb3a1af28dde47465b0","datavalue":{"value":"pumping","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$737A64D5-1E7E-4F2B-9601-7A90B682B590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dc9d8ec44fd1f6d9f11fbaeedf2f215712581c9","datavalue":{"value":"Sokolowski's criterion","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$C912DF06-C237-4200-B8D0-253B075E36D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28cb72acfb02595591b305d3c0134ff2223dd2ca","datavalue":{"value":"semilinearity","type":"string"},"datatype":"string"},"type":"statement","id":"Q794440$268C44A3-F22F-4799-9065-E75B75C54B11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"294e1560b692bac1dd7a61f0104c714c0eb36374","datavalue":{"value":{"entity-type":"item","numeric-id":594603,"id":"Q594603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$ACE9F09C-2D93-4902-ADB0-08EA7D47DDB5","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":"Q794440$8F654249-3CDD-4CC9-8E64-9EF22069926F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2a287346ee1076b728a5bf1d294c9ed3db8a6a7","datavalue":{"value":{"entity-type":"item","numeric-id":3967068,"id":"Q3967068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$4C5DA859-1A48-4252-BBCC-092CA8794D8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"292e4ab1fffc97690b951d2042777fb5b332bd1b","datavalue":{"value":{"entity-type":"item","numeric-id":3912051,"id":"Q3912051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$8C8A513D-9105-45A5-B8AE-F7D488AACCA6","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":"Q794440$67E97BD6-5385-4449-AC92-A811A37F8085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeed94acd19ce7b58256979762d2639e958be258","datavalue":{"value":{"entity-type":"item","numeric-id":4168085,"id":"Q4168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$D3D0141A-452A-41C6-A673-6CB2A545B475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec4866ab6266879780901e35504fb81820cd5078","datavalue":{"value":{"entity-type":"item","numeric-id":4131055,"id":"Q4131055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$4D037C20-1E6B-4D8E-892B-9DBFE2767A62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5acae39981c04bee67afb40be4d3b17e459e9d6","datavalue":{"value":{"entity-type":"item","numeric-id":5668008,"id":"Q5668008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$DDFF5167-895E-46DF-BD82-1FCA51ED44E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ffa4c51a9cf5453739fa46eb9e9491652e79022","datavalue":{"value":{"entity-type":"item","numeric-id":1169297,"id":"Q1169297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$465A7C41-FFC0-4A58-A6B4-0B2AF5D10677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba4d01a97a3cd454f116ed0737edfdfcb9f7a69f","datavalue":{"value":{"entity-type":"item","numeric-id":5565120,"id":"Q5565120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$024C4775-A7E7-46B8-B83F-D541CEEF4310","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":"Q794440$6D7688B2-A149-48A3-8530-AD0A7168447E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0265ac0a57cf051e2c321f7c93b1985640733740","datavalue":{"value":{"entity-type":"item","numeric-id":1249046,"id":"Q1249046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$17B504B3-F998-4BDD-898B-34EAFA722297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3808120b904bbfe6f944551835118b1ca46d729","datavalue":{"value":{"entity-type":"item","numeric-id":1238637,"id":"Q1238637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794440$5DAC8707-0297-4EAA-94E7-77FFD5CF57FD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"593f37f389fddb817153f6d5e0286588cf5457da","datavalue":{"value":{"entity-type":"item","numeric-id":3982062,"id":"Q3982062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6901c43e123ea233f6004731ac2f9ff1864c722c","datavalue":{"value":{"amount":"+0.9518796","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$ED8AC7D0-2411-4977-98B5-E446A43F1C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"764376fad79476428375440a469004a80e0daa27","datavalue":{"value":{"entity-type":"item","numeric-id":3028359,"id":"Q3028359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d03034ef2ff87e5ed36687ac926297d3b13f821a","datavalue":{"value":{"amount":"+0.9510545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$7AA0EB8C-6251-4E3B-959F-1CDE74DB7CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d48576c963ca1b2477bfbf5e5908c9730fda7c4d","datavalue":{"value":{"entity-type":"item","numeric-id":5541336,"id":"Q5541336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be62876c6e642c320832aaeba30076e8987998f5","datavalue":{"value":{"amount":"+0.92679155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$03041F79-144E-43CF-A3C3-FD43AB246899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d612054c1b05d9eaf486a4e3e33e6ed244b395be","datavalue":{"value":{"entity-type":"item","numeric-id":1570831,"id":"Q1570831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"672755fa5f8f3f9a34132932dfee7fce5537a71d","datavalue":{"value":{"amount":"+0.92422295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$4446FE26-4C85-410D-A11B-92ABA56D0DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8a8546d7e6b61a3845403d9bdbf4fe13c2193c0","datavalue":{"value":{"entity-type":"item","numeric-id":1092674,"id":"Q1092674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5f5f3783c325c6e2c559a35733c0999becddac2","datavalue":{"value":{"amount":"+0.916239","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$D00F3E1A-B7FA-4C56-BD32-B380AE32021C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff15a2f81012a2c759241e5101ab3576d5afbf0","datavalue":{"value":{"entity-type":"item","numeric-id":3345795,"id":"Q3345795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c206d0a470ed159e291856de69900934c7a22af","datavalue":{"value":{"amount":"+0.91370595","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$38CE9634-C0EA-4A89-9017-C4F3DADFD30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"570234ba6ae1c640f1df052d5503993d79ed0c7c","datavalue":{"value":{"entity-type":"item","numeric-id":4007589,"id":"Q4007589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a04e3e633b96b81692e788d9147f37310dfca2c","datavalue":{"value":{"amount":"+0.9122551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$02DC076E-FDB7-4144-ABAA-7052BFC185CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e90f4c6b26a566a68b1040d6cf1cad160b8f7458","datavalue":{"value":{"entity-type":"item","numeric-id":1276509,"id":"Q1276509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5de9b17a3bf1ba692b21fa247fd5d695aa50433","datavalue":{"value":{"amount":"+0.9112001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$CE147B89-735E-4EA8-AEC6-917F62CC7E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52ba5bcdc2350007ef56b9224e042c7d7576c344","datavalue":{"value":{"entity-type":"item","numeric-id":1825945,"id":"Q1825945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"463def15eee64a60c78405c30c11667fd2c80578","datavalue":{"value":{"amount":"+0.9110199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$C856DFD9-9EDD-4AA1-AA2F-A4C87D405D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1321e2bf633defa40bb4d5b9575c205f438894fa","datavalue":{"value":{"entity-type":"item","numeric-id":3742751,"id":"Q3742751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4354d38e37c555c1931b9bff2309553865329e94","datavalue":{"value":{"amount":"+0.9099765","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q794440$06D3EF68-3B52-4DD4-98C7-47A74C10F684","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On context-free and Szilard languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_context-free_and_Szilard_languages"}}}}}