{"entities":{"Q438589":{"pageid":440356,"ns":120,"title":"Item:Q438589","lastrevid":61924851,"modified":"2026-04-11T02:35:19Z","type":"item","id":"Q438589","labels":{"en":{"language":"en","value":"The equivalence of tree adjoining grammars and monadic linear context-free tree grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6062069"}},"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":"Q438589$4E5BA737-B63C-4F2C-AFA8-515604F76100","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e8c425dc8a5ee46dc32baada1914f2a991891096","datavalue":{"value":{"text":"The equivalence of tree adjoining grammars and monadic linear context-free tree grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q438589$2E2DC631-AC63-4F00-941D-50BD3930F570","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a14e6d916d444d35e14c8746d4dd4c28d1466762","datavalue":{"value":"1274.68151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$578652AA-FB23-4310-8BFB-140FE952AA1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"15f40494622acdfe788b016e3ef48205476f2ba8","datavalue":{"value":{"entity-type":"item","numeric-id":438587,"id":"Q438587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$CDAE7E4E-ED9A-40B4-B425-A7246E39B366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"75bddf16b49c9f22ed6e2af9e9a294dabc26d734","datavalue":{"value":{"entity-type":"item","numeric-id":371991,"id":"Q371991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$FA6CF289-A560-4B3E-BE9A-EA8E4B135636","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"147edfc9dddd5bbefb3ef0a24d334c7da90bbf45","datavalue":{"value":{"entity-type":"item","numeric-id":195246,"id":"Q195246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$560C27D6-4219-4B66-98F3-462BD47C424F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6c7ad691786690cf86127845d28cf47311748286","datavalue":{"value":{"time":"+2012-07-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q438589$6461D0EE-58D4-4072-AB30-EC33E58E2589","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7566fc58f60113e0e1aae49229c6c50fe3ba6af2","datavalue":{"value":"Context-free tree grammars have rules that allow to replace a non-terminal node in a tree by a whole tree. They are widely used in different areas in computer science. (Non-strict) tree adjoining grammars, originating from the examination of natural languages, only allow the restricted replacement of a node in a tree by a complete tree drawn from a finite collection. Their importance in linguistics stems from the fact that they are strictly more expressive than context-free (string) languages and seemingly sufficient to describe natural languages, but still efficiently parsable. The two grammar types are known to be weakly equivalent in the sense that they describe the same class of string languages. The present paper shows that they are also strongly equivalent: they generate the same class of tree languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q438589$B255CF79-2B41-4404-BD67-8155D86329F9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$197C46F4-2FC0-47F9-893B-5CC4D59EDA37","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$4A9CAF6A-A805-4525-8A61-5E277B34E6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$5410D32D-E1C7-4046-8065-BD608E7D8F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$A8C6DF37-33E4-4464-B301-B150D43EE40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$C98A2F2F-D3DC-4840-8AEA-9FF1EE2D7C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3b0a22587432575dd8ab8708980328a5eeb487a8","datavalue":{"value":"91F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$D22AACDB-291F-4F08-A1F2-13F07D271782","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"81750b8e5117bd87d769d4dbf17afbbacaf185e6","datavalue":{"value":"6062069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$8D3E9B20-C511-4A45-A9BC-A424FB0C4535","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f22839511b1b2e88121e4d8d7f81e307f8961a75","datavalue":{"value":"tree language","type":"string"},"datatype":"string"},"type":"statement","id":"Q438589$98E951A3-78E0-421F-AC7D-54561D77FC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee8b57110b3cb878b891083edebfebd2d9f94c6d","datavalue":{"value":"tree adjoining grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q438589$505E8FBE-F182-44C5-9166-6B96FD7A244C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c15cb892d3a126523880791e7c87a63028c88364","datavalue":{"value":"monadic linear context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q438589$90A92766-2B0D-484E-AB2A-28EFA8099FFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q438589$4D7EBE33-1DA8-4499-ABD5-30804B36ED98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86589ce8d4ac9a576aff5cc8d72f0756f3a589fc","datavalue":{"value":"model-theoretic syntax","type":"string"},"datatype":"string"},"type":"statement","id":"Q438589$CECBB33A-FEDE-4B3D-8F45-FBA8A6D0F981","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":"Q438589$FBA02F44-747C-416F-A3A4-CFD95D26737B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"803197f647d4496c4ea038ce9393e7b2cb9cef4d","datavalue":{"value":"https://doi.org/10.1007/s10849-011-9134-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q438589$D8DDF981-20C0-43E1-A59A-96D6F21D822F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fcf9efdf1f25c70328d82df567c3185175b6551a","datavalue":{"value":"W2049167443","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$75E316F4-8394-44A8-84E8-631103278E60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d74feebd6aeb7b6a39ed2486078ddf173d7310a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241985,"id":"Q1241985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$141B253B-D627-418C-8901-09088DE506D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b49e3241d6986489de950eb670ba8915d04e68","datavalue":{"value":{"entity-type":"item","numeric-id":835003,"id":"Q835003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$F8BD3E8F-CA70-4329-867A-C98B5FDDFAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86dd733dcbb769658e71110962ed733baf2c222d","datavalue":{"value":{"entity-type":"item","numeric-id":1969437,"id":"Q1969437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$6805E669-0296-4B8A-963A-835F492BB4DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e34b733d5c968f4670211735e85d54b3608649","datavalue":{"value":{"entity-type":"item","numeric-id":1225947,"id":"Q1225947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$7D1FF66A-3D5A-46A5-AFAB-125D9D6BD608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"143797a22c6b7bf746b572a3e85126e0e3c674af","datavalue":{"value":{"entity-type":"item","numeric-id":2368942,"id":"Q2368942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$FF4D1C88-6634-44BB-9360-22AEB4235597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b3dc91d180aff1a6a89713967853e6e2d4b99f5","datavalue":{"value":{"entity-type":"item","numeric-id":4506444,"id":"Q4506444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$6252F5E7-AE18-408E-B964-B1AFA3FE83BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0acfabb989ca79bd6f9ae1185a99b0968bcac1ec","datavalue":{"value":{"entity-type":"item","numeric-id":4954002,"id":"Q4954002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$2EDBBB17-BB19-4F6F-83CB-11FE8BC74121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8dbb9c9e7f4754c539a0d5c8828af6fd114f435","datavalue":{"value":{"entity-type":"item","numeric-id":1870569,"id":"Q1870569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q438589$445433D3-BFBF-4151-B609-0976655E8403","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82febf356319e34fc4e3e3da82aad3e2da62ed31","datavalue":{"value":"10.1007/S10849-011-9134-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q438589$859F91B7-043D-4994-ABF6-6423BA106EB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf394e6b33cade59103b34b2524455d053e31681","datavalue":{"value":{"entity-type":"item","numeric-id":3585002,"id":"Q3585002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","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":"Q438589$62DFFA45-EC29-4842-AD71-D8B096A2045C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4293c157e2fd2c31a44293f36fb0fde12b7fbfe4","datavalue":{"value":{"entity-type":"item","numeric-id":835003,"id":"Q835003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69d20f3436e75181d96df132f325c18b3ec88fbf","datavalue":{"value":{"amount":"+0.89697534","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":"Q438589$BCEBBC76-3E39-42B7-B5E6-E4C60416F38B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3090e24f428e952cdbeb640e1b27ce31b73850d","datavalue":{"value":{"entity-type":"item","numeric-id":3618604,"id":"Q3618604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a923e82a7d0f4b3385723b92d7b8f9824a25844a","datavalue":{"value":{"amount":"+0.8892126","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":"Q438589$F4037B21-0FFC-47B5-A38C-E2EAB896E1E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a4d6611769ea38033c0e94949bbf5757dad5f8b","datavalue":{"value":{"entity-type":"item","numeric-id":2921946,"id":"Q2921946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49f50b528407cf76a35d98ba23c5ff06b9c8cab5","datavalue":{"value":{"amount":"+0.88620067","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":"Q438589$51453A25-613F-4E72-83F7-D626E8B3B660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16605ab7248c4b392b9e9d6dd6cedcfc7c07a167","datavalue":{"value":{"entity-type":"item","numeric-id":4825389,"id":"Q4825389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf47dd3a30503461b73c2b0f48617b9452843a3c","datavalue":{"value":{"amount":"+0.88288724","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":"Q438589$58A6EC4C-5083-4B8B-9866-2D13FEC8DF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a267a20766342b47fb94f0802f84975dd7e9972","datavalue":{"value":{"entity-type":"item","numeric-id":4273674,"id":"Q4273674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0080c994ee1260a7647b86a88a38694c6d292a32","datavalue":{"value":{"amount":"+0.87891704","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":"Q438589$B4ADEA5B-BA6E-44ED-B0E0-F7FD731FC463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b49987c6244ed664565c2d3dcd917048b6dfd3c","datavalue":{"value":{"entity-type":"item","numeric-id":4923565,"id":"Q4923565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"099e3d6724a664e0a10430c9b9dfb20c75c06003","datavalue":{"value":{"amount":"+0.8782921","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":"Q438589$C84AA8AC-01DA-4104-8C9F-B7289EAB7878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f02a7d63ef2bca2f9400b8219b4d2b320d48a61e","datavalue":{"value":{"entity-type":"item","numeric-id":4370236,"id":"Q4370236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8391021f1df45d3c69c1d2899e0b58f14fa5cf6","datavalue":{"value":{"amount":"+0.87453103","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":"Q438589$B4F451B0-019F-40E8-B741-65DC4938E98F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"584e65c60210dccefc5a76debb71818108d88b8f","datavalue":{"value":{"entity-type":"item","numeric-id":5886207,"id":"Q5886207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dc5130fa02cac684ad200afd56e48fb64dd21f8","datavalue":{"value":{"amount":"+0.8732365","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":"Q438589$3D75DBCA-AB03-4ED7-88F9-BCB6101542B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e195b49f32414c03aaf589d1d742c3e2b4f4186b","datavalue":{"value":{"entity-type":"item","numeric-id":1679974,"id":"Q1679974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbb55e99d8f39a6ad879bda63b32496bc39f244e","datavalue":{"value":{"amount":"+0.8672954","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":"Q438589$81CAB71C-964E-420C-A169-DCC682EE33A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The equivalence of tree adjoining grammars and monadic linear context-free tree grammars","badges":[]}}}}}