{"entities":{"Q1198013":{"pageid":1208762,"ns":120,"title":"Item:Q1198013","lastrevid":66846903,"modified":"2026-04-12T13:15:20Z","type":"item","id":"Q1198013","labels":{"en":{"language":"en","value":"On the structural grammatical inference problem for some classes of context-free grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92084"}},"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":"Q1198013$3E119A6C-4C2B-4ADF-97F5-AAB1F357AFEE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea92db81b50524cb2c856b52a37fb46b18f4b1f5","datavalue":{"value":{"text":"On the structural grammatical inference problem for some classes of context-free grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198013$07CE3139-F079-4C38-9772-8777C891C125","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ef5af8b09f008147c997ae32ae2600162b50544","datavalue":{"value":"0779.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198013$6DE4F783-855B-486F-BEC6-FA35EB547EB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"21d286686e470b124ec4ea1c4499f32ba862f114","datavalue":{"value":"10.1016/0020-0190(92)90124-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198013$2126AD1C-8824-411A-AF7A-C0F0C831E0F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$B8EE9A40-C3CA-42BE-A4C0-BDC8751F09F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198013$E1470BF4-39B3-4863-98E5-7D3C598066D8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21e0a126d28ffd711eb8ee13710acc3b0631ac23","datavalue":{"value":"Inference from positive data is strictly less powerful than inference from positive and negative data [\\textit{D. Anglnin}, Inform. and Control 45, 117-135 (1980; Zbl 0459.68051)]. As a method for compensating for the lack of negative data, \\textit{Y. Sakakibara} [Theor. Comput. Sci. 76, No. 2/3, 223-242 (1990; Zbl 0704.68067); Inf. Comput. 97, No. 1, 23-60 (1992; Zbl 0764.68051)] has considered the problem of inferring context-free grammars from structural information. Given a finite positive sample, i.e. a set of words belonging to the language generated by the grammar in question, and the derivation trees of the works with unlabelled internal nodes, Sakakibara's algorithm finds out the reversible context-free grammar consistent with the sample. In other words, Sakakibara's algorithm solves the structural grammatical inference problem for reversible grammars.   The purpose of this paper is twofold. First, we consider the time complexity of Sakakibara's algorithm. Second, we introduce a new class of context-free grammars, called type invertible grammars, and consider the structural grammatical inference problem for this class of grammars. The class of type invertible grammars is a subclass of reversible grammars.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198013$E7FA8879-54FC-4E2D-9C63-ABCF9226F2D5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198013$7BF32AA6-092F-4463-8AC2-2DFC91F10BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198013$FC62433C-DC18-406C-87F6-DE95587CD4CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198013$C7E463F2-6329-4F3A-AF97-19A955C11FCF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67912681eb3074e222e413ccc454865671b8f689","datavalue":{"value":"92084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198013$819FFE6B-C193-4307-AE15-558315FD5049","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198013$1A3EA4AC-FB12-409D-ACD4-576775C9DB93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab75d76ed81b8897eaefd32d809161a669eee4f9","datavalue":{"value":"reversible context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198013$1B1540A2-48BF-4118-AE46-A59BEF00F39D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efffc1e5a25fedbae0113fb638db2939eddcf48a","datavalue":{"value":"structural grammatical inference problem for reversible grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198013$407ADC18-19FF-44B1-A058-0EC8B6C19FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198013$E9D23607-FEAA-4392-B46A-F92D6CD3712D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b737f2134298b4709702be411398ddfc8d45a239","datavalue":{"value":"invertible grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198013$74F9B3C4-8D70-4E60-8F09-06395067AC47","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":"Q1198013$C69D3475-6A67-4736-997C-F8276D3EC12B","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":"Q1198013$AA1EC895-8183-4E5A-9F89-BCBD36480D37","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b40c59feb183e6f32a8e2fcf3769d2018e89bfa","datavalue":{"value":{"entity-type":"item","numeric-id":3910029,"id":"Q3910029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$A24F8723-87F3-474E-8EB7-E94FBA3899AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1252d1a75df811aa2d125851fb76a199b341c5fe","datavalue":{"value":{"entity-type":"item","numeric-id":3945599,"id":"Q3945599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$25B3B890-D71C-4EF7-8202-D44363F88A48","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":"Q1198013$241C1C29-B6F4-4232-8E75-29E7D5811922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"642ecce3afc35aaf9c5ac09d2d3e3c67c45ececb","datavalue":{"value":{"entity-type":"item","numeric-id":917317,"id":"Q917317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$854F4116-E565-41A6-9929-C3CF8BE27740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$75E3379B-17CC-4FB9-BE21-ED0DA7CC084B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"829a26bf5c2632f72926fc206d00a26bd3ea52ab","datavalue":{"value":{"entity-type":"item","numeric-id":1186808,"id":"Q1186808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$6AAB0D3C-956D-4A6B-AB01-1F8A1E28B787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac5ae8518bf7a9518ea2049a5098af0633d94a50","datavalue":{"value":{"entity-type":"item","numeric-id":917318,"id":"Q917318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$865B101A-C506-40B0-827F-3E4D39D655E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e9366c82f8a71633f567b778add8be59a85724d","datavalue":{"value":{"entity-type":"item","numeric-id":3769963,"id":"Q3769963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198013$8EFC1E48-2439-4445-B53E-C352F755B438","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a11ba4d17b48165aab4ca891c1f471d6253c55d","datavalue":{"value":{"entity-type":"item","numeric-id":1205715,"id":"Q1205715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a9f573911b600490a65e5d3797518fa9ca65da1","datavalue":{"value":{"amount":"+0.86125648021698","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":"Q1198013$832D7E1C-0439-4B07-A487-4B45D746CA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98da57273317d5d7586cce6ebcf2c92003609256","datavalue":{"value":{"entity-type":"item","numeric-id":1186808,"id":"Q1186808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fff2787c7113d75c33338464a32067d868b1745d","datavalue":{"value":{"amount":"+0.8149254322052002","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":"Q1198013$DEB6AD26-FBA0-4BB3-8208-FCF4BE183E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fe9e80ddf902ec128828072973c753707cd1883","datavalue":{"value":{"entity-type":"item","numeric-id":3588379,"id":"Q3588379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1521bd68121d44cb8a1998b183f5f453ac14ac9","datavalue":{"value":{"amount":"+0.8112937211990356","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":"Q1198013$FEEAD7FF-00B0-49B2-AC62-3D566A7BB11D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a6aa0b0da57b09084cc9ba828b82dfb103ca45c","datavalue":{"value":{"entity-type":"item","numeric-id":5493036,"id":"Q5493036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38df851e2f25cdf32c243ada9b44235f375db904","datavalue":{"value":{"amount":"+0.7957876324653625","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":"Q1198013$54C799E0-E59D-4E27-84A0-01CD998751FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94628c03f9589bdcd05eb17bbcf746745826defc","datavalue":{"value":{"entity-type":"item","numeric-id":2714262,"id":"Q2714262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81ff5ea8ab162422dd0d0fdc1c9e580fab1eb1ad","datavalue":{"value":{"amount":"+0.7909866571426392","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":"Q1198013$0C21382C-D1AA-4D91-9324-606DC0A379F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the structural grammatical inference problem for some classes of context-free grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_structural_grammatical_inference_problem_for_some_classes_of_context-free_grammars"}}}}}