{"entities":{"Q1920229":{"pageid":1930971,"ns":120,"title":"Item:Q1920229","lastrevid":43422536,"modified":"2025-07-25T16:51:13Z","type":"item","id":"Q1920229","labels":{"en":{"language":"en","value":"A hierarchy of uniquely parsable grammar classes and deterministic acceptors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 918713"}},"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":"Q1920229$878494A3-8366-493A-8F05-D4991F624144","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0dd221e50695b014f228518469dc34c136b2e9b3","datavalue":{"value":{"text":"A hierarchy of uniquely parsable grammar classes and deterministic acceptors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1920229$3EC18225-D49A-4521-A005-230F2DDCE5AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f92e99516ee616d2f7303a517de195bd452e8c44","datavalue":{"value":"0865.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$34FF8476-0066-441F-B467-0B256E8ABE95","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"182d2a53e16892f59ea178d1cc15214afb3283bc","datavalue":{"value":{"entity-type":"item","numeric-id":235713,"id":"Q235713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920229$49927923-D5AB-4905-9C26-D27FCA2341C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba0d409e8a1cbf73363f55e2b4a09f14f48ba9dd","datavalue":{"value":{"entity-type":"item","numeric-id":1920228,"id":"Q1920228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920229$4B1BAD40-27DF-4786-A96A-D61BFCF2A431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a069ea3e03615f4b7666ce79754e7b5b6c24f5e","datavalue":{"value":{"entity-type":"item","numeric-id":1062462,"id":"Q1062462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920229$845FABD9-9921-4234-86DC-24086903D7E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"46bdfa4b5a3cb55567ca2c775a0af40d2468195d","datavalue":{"value":{"entity-type":"item","numeric-id":940516,"id":"Q940516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920229$9741FDC0-5A3E-4015-B62D-62ED40EE2FB7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920229$3EAD7111-67EB-49AC-B94B-84A07E8998ED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c52e4811fffdb8f318da6437d640586a60136db4","datavalue":{"value":{"time":"+1996-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1920229$205D1143-ABB1-412C-922C-632EAA90D6BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a41365157c0bc06ce800372f4a2ce103c0b90be3","datavalue":{"value":"We introduce a new class of grammars called uniquely parsable grammars (UPGs). A UPG is a kind of phrase structure grammar having a restricted type of rewriting rules, where parsing can be performed without backtracking. We show that, in spite of such restriction to the rules, UPGs are universal in their generating ability. We then define three subclasses of UPGs. They are M-UPGs (monotonic UPGs), RC-UPGs (UPGs with right-terminating and context-free-like rules), and REG-UPGs (regular UPGs). It is proved that the generating ability of the classes of M-UPGs, RC-UPGs, and REG-UPGs are exactly characterized by the classes of deterministic linear-bounded automata, deterministic pushdown automata, and deterministic finite automata, respectively. Especially, the class of RC-UPGs gives a very simple grammatical characterization of the class of deterministic context-free languages. Thus, these four classes form a deterministic counterpart of the classical Chomsky hierarchy.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920229$B1F68D06-F79D-4321-BFB9-0C7C2046D68C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$D6FFB7AC-F6B3-4D7F-8BAF-D46F916595D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$27B11B42-FCF0-4A89-9546-75CFEC5F6283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$088DF3B8-D93D-4D8A-B599-1B78D15AE237","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b145d3966d43a33bac9e0d4347746420f1b5afd","datavalue":{"value":"918713","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$04BF6A93-B93C-4C78-92EA-ED8C62F99853","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d4915b420a1b81b37d9817be32007c619ef05f3","datavalue":{"value":"uniquely parsable grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920229$1964178E-C6E9-450C-B94D-4976123A8FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99c2b0c07c4b41c6b99a5b29ee887eed24383bd6","datavalue":{"value":"phrase structure grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920229$E2CBFA59-F846-4C90-BF5F-B42170390F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"237bb64abe07c31904fc0e8e2ddf2df232747977","datavalue":{"value":"rewriting rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920229$5C9D4F77-E8FA-4AA8-8F3D-051AF4759FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a0c7bb0ecf32b900347362cf461885c46f832ca","datavalue":{"value":"parsing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920229$0322D759-AE01-4C3D-B39A-A93FFCECF122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8be482fe6cb276a437ef8e80db0734f84bfca34a","datavalue":{"value":"deterministic context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920229$43847862-4F35-40EB-9BA0-DED9BF5B99C7","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":"Q1920229$A7E2D522-56D3-42B5-B166-A18D2A1EFA2C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ad0da84933ac25c8b095302489a20db5ccaad9d7","datavalue":{"value":"https://doi.org/10.1007/s002360050091","type":"string"},"datatype":"url"},"type":"statement","id":"Q1920229$FAF91877-4831-4CFC-8E77-9A99EAC87DD3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1713c231ff8dba47032d2db9647b5a41db9655bd","datavalue":{"value":"W2021531207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$CA7F0764-F68E-4E9F-9A3F-88C323748916","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8042606dece7a4d34b2d8ea39d712cb27a9d47ff","datavalue":{"value":"10.1007/S002360050091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920229$8333C646-EA22-4602-9758-468C019C9ED9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"341eaa1736d7c38d42ad9c85eb184e756509e15f","datavalue":{"value":{"entity-type":"item","numeric-id":4520809,"id":"Q4520809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4b595a24f785aa03b37f81b796834db05c3293b","datavalue":{"value":{"amount":"+0.9237584","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":"Q1920229$9AF02E23-7097-48FE-A221-577FC3BEC70C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65b7c8ee55fbdb700ba0a5ba0b9d065e909d7f85","datavalue":{"value":{"entity-type":"item","numeric-id":1841065,"id":"Q1841065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c3ce891788f837c50d4e4a164b530e5eaa397ba","datavalue":{"value":{"amount":"+0.8838228","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":"Q1920229$273EAEE2-CED5-42D8-A43D-86EA4F547939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10923dcc48f9d3988331c1c752e0bf0974e8af90","datavalue":{"value":{"entity-type":"item","numeric-id":3313284,"id":"Q3313284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abebb8c835956b9e3d3fc828154b804dd804115a","datavalue":{"value":{"amount":"+0.88000154","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":"Q1920229$E60BA6DE-DA1A-4711-9716-6327B1CBF909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"465dd3347d15b404aaaec4189f371942880898de","datavalue":{"value":{"entity-type":"item","numeric-id":5053741,"id":"Q5053741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0519f369efa2df8741b93a9b62ee67a19fa24a11","datavalue":{"value":{"amount":"+0.87141544","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":"Q1920229$3EE0071C-723B-410E-AC77-A823A7DBF4B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4991867a97c2110e4746a79515b5395a7b58047b","datavalue":{"value":{"entity-type":"item","numeric-id":1080666,"id":"Q1080666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89ed6c7f1c747f6d8081820b0ef714f35fa3e6e8","datavalue":{"value":{"amount":"+0.86644864","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":"Q1920229$3C3B6702-2D50-4784-930E-E3DB4B124759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0703ed55e613493994d68ec442b3e771bb5bc887","datavalue":{"value":{"entity-type":"item","numeric-id":3316617,"id":"Q3316617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89ed6c7f1c747f6d8081820b0ef714f35fa3e6e8","datavalue":{"value":{"amount":"+0.86644864","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":"Q1920229$35EC6771-4833-44A8-A8CB-E97197F97336","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b0de635a303f834a0b1c0c7963181f27422f112","datavalue":{"value":{"entity-type":"item","numeric-id":1777374,"id":"Q1777374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"386368418157ee88df0f0b4b8468caaf5c8a5cad","datavalue":{"value":{"amount":"+0.86130285","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":"Q1920229$1E13B06B-CE12-48AE-9DA2-ED29ADFB7D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb22e19e7f61d7ae0f3cea256cb2fa1770bef562","datavalue":{"value":{"entity-type":"item","numeric-id":4793127,"id":"Q4793127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b61d8dec3b2b1779cc51ad9005111f7b5f105ca","datavalue":{"value":{"amount":"+0.86122036","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":"Q1920229$F7B03351-92EF-4FB6-BE42-ADABDE48B103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad52342074112ccc8bae6e3d927a3c40d1fab864","datavalue":{"value":{"entity-type":"item","numeric-id":4365821,"id":"Q4365821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35b2aea25a4f3542a27c5d4ae1a2a027748c7440","datavalue":{"value":{"amount":"+0.86108965","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":"Q1920229$C2E1684D-D014-4F54-AA36-51E2BABD82E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58209049448f75a1b4cf927761ce96cb1edc899e","datavalue":{"value":{"entity-type":"item","numeric-id":3450205,"id":"Q3450205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21c91fac091d5db0e52ff563cf51dfe60e36d64f","datavalue":{"value":{"amount":"+0.85841227","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":"Q1920229$F88F4603-3AA7-4CAA-87F4-71D29EE844F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1920229","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1920229"}}}}}