{"entities":{"Q807023":{"pageid":808871,"ns":120,"title":"Item:Q807023","lastrevid":64480806,"modified":"2026-04-11T20:10:16Z","type":"item","id":"Q807023","labels":{"en":{"language":"en","value":"Decidability of structural equivalence of E0L grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4205995"}},"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":"Q807023$21F8517A-EFA9-4771-8D60-FBBB5FD5C27C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3acf427ad98415367a7852cf70b6f5d0c9a057de","datavalue":{"value":{"text":"Decidability of structural equivalence of E0L grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807023$D8CAADDA-1604-43CA-8FCA-47C3F2C6A900","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bea80ce9ae4c6d7359e57dbefe9292e55d4ee004","datavalue":{"value":"0729.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807023$D593A16E-EDE0-4D8D-B94F-C0C0B90D1FB8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"592dc2786e371d7a759a3a6d811cde810bcb615e","datavalue":{"value":"10.1016/0304-3975(91)90176-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807023$22C5E98C-91AA-4D0A-AD4E-F71538F61FA5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8455035442168fbb99576351474dec2ff822256f","datavalue":{"value":{"entity-type":"item","numeric-id":247255,"id":"Q247255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$C8FD73DB-AC08-479A-A2D3-6F5EAF26032B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f143d75162aea6d3b09de1ba925afc74ef470da4","datavalue":{"value":{"entity-type":"item","numeric-id":418765,"id":"Q418765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$9C07EE33-3011-4837-AB6C-63BF203EA1D9","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":"Q807023$C4CC3902-A4F2-4E03-9814-85A379275315","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q807023$FBED4BCC-7241-40D6-98D6-8994D67D4A5E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f1bcbf75c28ea99d6df6e0ea4ddee03ad4215494","datavalue":{"value":"Two EOL grammars are said to be structurally equivalent if they generate the same sets of teminal syntax trees when one disregards the nonterminals labeling the internal nodes of the trees. The authors prove that the structural equivalence of EOL grammars is decidable, thus solving an open problem posed by T. Ottmann and D. Wood [Structural equivalence of EOL grammars, Research Report CS-89-40, Univ. of Waterloo (1989)]. The proof is based on the use of so-called height-counting tree automata which are finite bottom-up tree automata that remember the heights of the subtrees processed so far.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807023$22B27F3E-21F1-4906-979B-441A1969FFCB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807023$6F34DC3B-91C3-4A62-AFE0-359FB71D71B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4269b3ca621684b00a81082d95345981164255c8","datavalue":{"value":"4205995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807023$4ED13333-848C-419C-8D63-71B870A4E565","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a049b8157ce822430717103afcf642fe2966ee6d","datavalue":{"value":"structural equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q807023$EF0832FB-3E6E-4922-ACB4-EE857D524D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7109ea366b657ce5fbc64bb42bbdd180f8b295ec","datavalue":{"value":"EOL grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q807023$ACCC30A1-BE33-4FCD-A205-1B5D24A91355","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a9fe589b6a50c4cc9da51bba6b47c6e6be0f84d4","datavalue":{"value":{"entity-type":"item","numeric-id":1171886,"id":"Q1171886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$5F5E31D9-005E-4924-8EA4-29DEA72C25A8","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":"Q807023$37BF910E-90FE-4B6A-B9D3-D8554BE3058A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b9a0f8c0c80995171c83df43b03ffa02091ba4e3","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90176-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q807023$3A1E7EF7-BBA2-4721-B66D-A8829F758FD1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14e6bf037fe00d45f6a31e237ce65a564f3c7879","datavalue":{"value":"W2023379232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807023$0AC8CCE7-22C6-455B-83E2-8BC14ED29C56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1de9637af9a8fedcf8ab07e9c2d71e01bf8c23d8","datavalue":{"value":{"entity-type":"item","numeric-id":5565119,"id":"Q5565119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$40103EFD-C3D4-419F-8C98-D5330CC2C1C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5709c2ffa01c029b486c6e705fa60fd703dea1c8","datavalue":{"value":{"entity-type":"item","numeric-id":4179852,"id":"Q4179852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$00C6EC93-58A7-469F-B73A-66D502357542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6126eda57d6fa709d095c73ea2e69f001a129d7b","datavalue":{"value":{"entity-type":"item","numeric-id":2525996,"id":"Q2525996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$F56348FA-6911-4260-BE3B-02CBF7767D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdf9c2e8005e070cc02f7e5d2e34924b80464613","datavalue":{"value":{"entity-type":"item","numeric-id":5553283,"id":"Q5553283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$BC097A04-A257-4EB4-911A-CED603F7E36D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72b16202b732c4e789b0a77fb94af043c389acb4","datavalue":{"value":{"entity-type":"item","numeric-id":1179185,"id":"Q1179185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$95B874E6-0986-40CE-A180-541AE20B39EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3435a074a27b4cf400b07a40abf5a945a67b0078","datavalue":{"value":{"entity-type":"item","numeric-id":4036764,"id":"Q4036764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$D99EC746-E027-4E1F-A809-623726C7FCA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dec3fbe30a0898036e24c433715320d7367f7a4c","datavalue":{"value":{"entity-type":"item","numeric-id":2534284,"id":"Q2534284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$A2479B76-2AFE-4E1A-86D1-81C29D777143","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":"Q807023$7EE0175B-D543-4FDC-8111-53186A106C27","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":"Q807023$6ADE2A3A-C5F6-49EB-8A4F-4CB18E586E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d617310b37fc85fd09ec7dd2c4fe23b8a3c75fd8","datavalue":{"value":{"entity-type":"item","numeric-id":4692941,"id":"Q4692941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807023$12FEB38B-D66C-47B9-AB5A-28B9C75FF1A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9114f1d412a7c41a6b673f36c0b60ff560b6bad4","datavalue":{"value":{"entity-type":"item","numeric-id":5894883,"id":"Q5894883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfc6edaa759ac984b18067907e84e1655c1c14a6","datavalue":{"value":{"amount":"+0.8843629360198975","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":"Q807023$CBB1B16A-EB7B-451D-A99F-CE5C9B3A46A6","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":"f2a6689351b638f38ffb53e28570de09c23a7984","datavalue":{"value":{"amount":"+0.8800001740455627","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":"Q807023$F6EFB294-3984-4D8A-88C9-33B8B146D31A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"351b001be47e562389917dc722f3b98ab0b0d748","datavalue":{"value":{"entity-type":"item","numeric-id":4217608,"id":"Q4217608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8be688000eaf67501b74f3b2a5fef6069d6a963","datavalue":{"value":{"amount":"+0.8781685829162598","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":"Q807023$E8BBCEF5-F9EF-40C1-8D55-9177D352DF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee9191f9ed4bc44c051a25d314d42214026c77f1","datavalue":{"value":{"entity-type":"item","numeric-id":671426,"id":"Q671426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9c360d8827d0b05c2bb298e8b24b5e79812445d","datavalue":{"value":{"amount":"+0.8720231652259827","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":"Q807023$139BFB89-8611-413F-8D81-C49241FBC8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4c9ec56f83fe15d2555ed1b1466188d3c91f2ea","datavalue":{"value":{"entity-type":"item","numeric-id":4036763,"id":"Q4036763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be37a1504eca11112845e552673993f0e717b7f3","datavalue":{"value":{"amount":"+0.869544267654419","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":"Q807023$F2CC3D7F-05DC-486E-98CF-3866B44C9B96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Decidability of structural equivalence of E0L grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Decidability_of_structural_equivalence_of_E0L_grammars"}}}}}