{"entities":{"Q1069311":{"pageid":1080063,"ns":120,"title":"Item:Q1069311","lastrevid":69562815,"modified":"2026-04-13T07:51:47Z","type":"item","id":"Q1069311","labels":{"en":{"language":"en","value":"The undecidability of form equivalence for context-free and EOL forms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934423"}},"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":"Q1069311$75F8EE45-6CCA-4D4B-BBE6-633F80EEDA63","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80d041ca7e67f23360d6232c1d6cb2c9ceb2d316","datavalue":{"value":{"text":"The undecidability of form equivalence for context-free and EOL forms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069311$165EFD13-1B81-46B0-9748-5204922B405B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f9e06483687718a5c50f0a7b746c72efee019bd3","datavalue":{"value":"0583.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069311$7E798261-DB12-467F-B51C-B7967C268CFB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"88ab9ebe73d84a70d6c507c0c182b80e6e5489c4","datavalue":{"value":"10.1016/0304-3975(84)90045-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069311$6847F1ED-D029-41C2-B511-7C1AB6429444","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01f16380557257b8ec44a38d0f814c5ab24da556","datavalue":{"value":{"entity-type":"item","numeric-id":1069310,"id":"Q1069310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$75C8FCE9-6CA6-479A-A47B-31DF59294D3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$2CD751E1-86E2-4147-84AE-5D4914F08333","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":"Q1069311$860811C0-14BA-4564-B502-36400ACC834C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"12af02b33614854985e6770cd887db044d67073e","datavalue":{"value":"This paper studies the decidability status of various equivalence problems in form theory. Most of our discussions concern the notion of a language form. We compare the form equivalence problem between language forms with the ordinary equivalence problem between languages. However, the main results deal with L forms and grammar forms under strict interpretations. We prove that the form equivalence problem is undecidable for (a) context-free grammar forms, and (b) EOL forms. The proofs of these results are based on our investigations concerning language forms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$88A56783-6A45-4BBC-9E21-F8A57B531457","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069311$64756B28-D7B1-43CD-822F-E89B7BFCCE20","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d283eb399c90ccb71017e5a51cbc376bc82e5b51","datavalue":{"value":"3934423","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069311$EF39E901-B224-4E82-B3C4-C363BAE9F247","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$647E0EB3-180C-4938-B184-DB3B2F349377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43210742d6a5811ab9c8cc6deb38597864a144b7","datavalue":{"value":"language form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$6918394F-FE46-4C0C-8715-14E92D93E8A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3146c8bf99ee108df02148241ba8496f5799cb9","datavalue":{"value":"form equivalence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$D5ACAD8E-7F5A-4F18-AEC5-C1FDFB0D52EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ec0596ccde4a31e5a298d765ac0e5fe0d97035f","datavalue":{"value":"equivalence problem between languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$393C30E0-5D41-4198-9573-1A7D926C2F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b829be4eec4ee450bb915341e0d15f17afe11cce","datavalue":{"value":"L forms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$310E9643-C493-4B29-AFE1-FAADCBA00D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2e79939fbf7a4837176b286c24e614fbf058214","datavalue":{"value":"context-free grammar forms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$88A6DDE3-C565-4890-8F66-3A7A1A6039DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3faeb60bfbb034a387e737b87b9baf999b5bcda2","datavalue":{"value":"EOL forms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069311$9A9122EF-56FE-4470-90D7-514AA438CF05","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":"Q1069311$0B10F233-B140-4820-85B6-C5F20E564525","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f2b5609f84c68957621042d0672d9c2f6ad7ba2e","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90045-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069311$3A8D1B93-C73B-40F2-8BF6-509DD7E1BA1D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"66a66a4c0c5adbfd9893911f88a22d2747b44f5f","datavalue":{"value":"W2011155708","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069311$6FCE1E93-55F8-4FE9-A523-ECD29C29CE5D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdec3e2dd9a711627d602e41930b5608c5ef4004","datavalue":{"value":{"entity-type":"item","numeric-id":1226865,"id":"Q1226865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$FED9F2FE-AB49-43FC-BC6D-D0A6C68E78FB","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":"Q1069311$384424CF-5DBC-4BFA-9C08-740AAEF6B697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25ff58590624fb02a3572fa7003fcbacc18b36a4","datavalue":{"value":{"entity-type":"item","numeric-id":3758252,"id":"Q3758252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$2EACA6C7-AAE7-45F0-9A7D-9656CC51D44B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b11a25457f5af26b48c6659f26f7e01c2b954267","datavalue":{"value":{"entity-type":"item","numeric-id":4746804,"id":"Q4746804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$7795C19F-F395-4BD0-B0E4-E6AE4534652F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16113eaa112ad0d652edecb4eb2e5bfe72648992","datavalue":{"value":{"entity-type":"item","numeric-id":1160490,"id":"Q1160490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$67F1313D-AB19-4063-9984-83DD88DED406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9500e19069722efa256e9656f8110bdcd87d826","datavalue":{"value":{"entity-type":"item","numeric-id":4140407,"id":"Q4140407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$1AD6279B-4861-43BB-9237-1F3534C79313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa7a343db226e6c7da9bd7db585a412df58862","datavalue":{"value":{"entity-type":"item","numeric-id":5678435,"id":"Q5678435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$C6B951B5-5065-480B-BF6B-80F15D702422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"946f257475ecab2da5dddb765b121d598553ce8f","datavalue":{"value":{"entity-type":"item","numeric-id":1055198,"id":"Q1055198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069311$A46A47C4-C132-4F68-805E-CC2549644D64","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"21565c80d99307b7944e46344b2d4d8919439140","datavalue":{"value":"Q126437697","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069311$C4AFDAB3-1F57-4980-BCDC-4156067566B9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5200efa6cfcff9f383957adcfb80b3f3e6e1a3e3","datavalue":{"value":{"entity-type":"item","numeric-id":1961239,"id":"Q1961239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ba111733efd3e51309b8660f28b96d10cac50ea","datavalue":{"value":{"amount":"+0.78768390417099","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":"Q1069311$5EC4E80F-AAFF-4E0E-8B1F-95E49B2E1105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba6555388a7ff1a60c553e4224be521ae2f0d4fc","datavalue":{"value":{"entity-type":"item","numeric-id":4284264,"id":"Q4284264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5c5a6257d463cfd7ac82281920f0d5e681c1d73","datavalue":{"value":{"amount":"+0.7643799185752869","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":"Q1069311$A55ACF59-EA33-4621-BE72-6A536980F6AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c5f13520bd7440b2a1c337516df0ac00b722e84","datavalue":{"value":{"entity-type":"item","numeric-id":1067789,"id":"Q1067789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ce6ef75350fb8a1a9240db849e4d8eaa7a5484e","datavalue":{"value":{"amount":"+0.7572406530380249","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":"Q1069311$548F683A-D58C-44CA-9B7D-E98A5D6DFB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"639c9981bb1b443f214de7f4a4328b7ec5fb3025","datavalue":{"value":{"entity-type":"item","numeric-id":1070829,"id":"Q1070829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70300de08267410332bb346bdcf585efed7bc3bc","datavalue":{"value":{"amount":"+0.7526864409446716","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":"Q1069311$D8038127-7649-42AF-8E14-D6B85AEC9670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59fc763dea8dfc392bf18363fc4fd231839b153a","datavalue":{"value":{"entity-type":"item","numeric-id":3140021,"id":"Q3140021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0da472f627678a08143b4a9089e928bcef6f27ab","datavalue":{"value":{"amount":"+0.7523586750030518","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":"Q1069311$276B6E94-B91B-460B-9E02-9CEED895BBD4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The undecidability of form equivalence for context-free and EOL forms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_undecidability_of_form_equivalence_for_context-free_and_EOL_forms"}}}}}