{"entities":{"Q802880":{"pageid":804728,"ns":120,"title":"Item:Q802880","lastrevid":49496074,"modified":"2026-01-07T07:55:47Z","type":"item","id":"Q802880","labels":{"en":{"language":"en","value":"An efficient recognizer for the Boolean closure of context-free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4199642"}},"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":"Q802880$84420CE6-DE21-4275-AF64-5DBD6862A8D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"136594df4e6b987c16075f3966da60e45c1ad957","datavalue":{"value":{"text":"An efficient recognizer for the Boolean closure of context-free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802880$59716E81-6543-4DF1-B013-24F90C4B28F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d0839d9b5640bd3db0bd4bd2cd554dab343996b","datavalue":{"value":"0726.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802880$92191079-DDE0-415B-A252-A32A3AB85F43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e369cda41da7b8deeb440bcb1e404d197e12a525","datavalue":{"value":"10.1016/0304-3975(91)90205-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802880$A763CD3C-B160-471F-A620-D0C1C5833620","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf95eb14a4ebf171fed78b9375bc92a218886427","datavalue":{"value":{"entity-type":"item","numeric-id":802878,"id":"Q802878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$7A4A75E1-FEA2-4785-A508-1AB86C820161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f777748acbf2ad13348533714b983787ec1a7c0d","datavalue":{"value":{"entity-type":"item","numeric-id":802879,"id":"Q802879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$1165D07B-AA5A-4728-98AC-E4B3806DFF77","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":"Q802880$4CE23B8B-44D8-44A8-BE85-0C22F61226AA","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":"Q802880$BEEAE1FA-2A91-40C9-9D40-ED85F5EC8B59","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f399c6d2dece0846e3e10cb447513e33c256ee2f","datavalue":{"value":"This paper presents a sub-exponential recognizer for a class of formal languages that are not contextfree. It is based on Earley's algorithm that requires cubic time and works for unrestricted contextfree grammars. The main idea is to extend contextfree grammars by allowing complementation and intersection operations on the right-hand side of the production. This means that, at a given position, a string is required that cannot be derived from a nonterminal A or that must be derivable from symbol A as well as from symbol B. This class of grammars generates the Boolean closure of contextfree languages.    The parsing algorithm is an intuitive extension of Earley's. E.g., a complete step can be applied if the point is in front of an intersection operation and there are completed productions for both symbols. The formal description of the algorithm uses some operations on sets of parsing predicates and requires a lengthy list of definitions. The correctness is proved inductively. An easy understanding of the paper is possible if the reader is familiar with Earley's algorithm and starts with Fig. 3c.","type":"string"},"datatype":"string"},"type":"statement","id":"Q802880$9476D373-DAE3-4A0B-BB6D-3126AD02F5BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802880$4B262E7D-834B-47D1-B89B-CF1A060C8FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802880$199AC652-33B7-4FF8-A1CA-868D674DE584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802880$7260B2D6-2EAF-4922-91C1-630CE802421D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0a687a72dc9eadb669af293341bc717880822c59","datavalue":{"value":"4199642","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802880$0CDDFC9D-96D0-4A24-B45F-2FC7B287645F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f99ff32fbd3b01b3be73467c4abd5a99fd01337d","datavalue":{"value":"Earley's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q802880$8268BAD7-B969-4E8D-881A-FD7C542FB2A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3929cb790e21a888c4dff01fa0c162b4ae90d188","datavalue":{"value":"contextfree languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q802880$9BFDC5D2-462F-4FBA-869D-77D41876D44E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"022fe16d37aa700fea70e7a830c42e0ea8776f70","datavalue":{"value":{"entity-type":"item","numeric-id":685457,"id":"Q685457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$B5242892-B3DD-4A84-9C6F-C2B8308C4D99","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":"Q802880$8A0D5125-817C-44DD-AF96-CA94C4DE0FF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b78adcee74e0f5ade00e0948eea875c91d9521e5","datavalue":{"value":{"entity-type":"item","numeric-id":5578055,"id":"Q5578055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$64CE5850-3FC4-44C5-AC51-E86F3765C8F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eee975ef5deaf81238105e966c5726499b315f80","datavalue":{"value":{"entity-type":"item","numeric-id":3911426,"id":"Q3911426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$990F1F2A-1485-4F67-AD0C-EE285F9AA976","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":"Q802880$9D3699FB-B63D-4532-BE91-9B3AE0650F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff2cf228e7f6980c3ee8de846819585d642e9839","datavalue":{"value":{"entity-type":"item","numeric-id":5536277,"id":"Q5536277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$58FA0343-37EE-4E1E-8B8C-D641BAB5B37D","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":"Q802880$37406B1C-3F55-49B7-9C7D-F1D542CE5F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16cf335d5b7594672e390f44ff0f73ea66ddcf55","datavalue":{"value":{"entity-type":"item","numeric-id":1219690,"id":"Q1219690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802880$3326C65A-947D-4667-8854-8DBB03F970F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aca0f9bc6f7c4a7584592cbb9f8fe2c15f8a4791","datavalue":{"value":{"entity-type":"item","numeric-id":5711962,"id":"Q5711962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9da2cd543e6449c23d7c07c6dd8050071349e0c2","datavalue":{"value":{"amount":"+0.795758843421936","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":"Q802880$75B4650B-FC48-4B9F-B9F4-E0357BE41244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00a7d065efadb3eb1c9078bd2037e09be4a6ef35","datavalue":{"value":{"entity-type":"item","numeric-id":929298,"id":"Q929298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a189129804abc5ce4f3f1dafbbc1fb2e2a481e60","datavalue":{"value":{"amount":"+0.7952747344970703","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":"Q802880$35D6C15A-1365-4B4C-84B9-C6A0541E7E1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"400bfa2e500e4e93c5d86316003b34471a63b7d1","datavalue":{"value":{"entity-type":"item","numeric-id":5473686,"id":"Q5473686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a965b286b9f503897aef007b973bbf6132ab1d80","datavalue":{"value":{"amount":"+0.7758658528327942","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":"Q802880$1C2E387D-008F-4EC0-A0E3-05B6C769CFA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1c4561cf63b911692e3a46331c4c2084e5964e8","datavalue":{"value":{"entity-type":"item","numeric-id":1886037,"id":"Q1886037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"369b5e6d55ab2a3cd166bcc77015aef78d74fc18","datavalue":{"value":{"amount":"+0.7750853300094604","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":"Q802880$D832A550-2A8E-49D3-A319-A2BCD8B5125A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"893554f17798dd5e8e5e8abc0b0a1511fe9ee90b","datavalue":{"value":{"entity-type":"item","numeric-id":2641876,"id":"Q2641876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af16cadc07a777c804d7e13124dff3775610c2c3","datavalue":{"value":{"amount":"+0.7709742784500122","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":"Q802880$C0956C39-5853-4508-824E-BEAFB893C072","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:802880","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:802880"}}}}}