{"entities":{"Q1209991":{"pageid":1220740,"ns":120,"title":"Item:Q1209991","lastrevid":69899508,"modified":"2026-04-13T11:05:00Z","type":"item","id":"Q1209991","labels":{"en":{"language":"en","value":"An execution mechanism for nondeterministic, state-oriented programs based on a chart parser"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 168865"}},"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":"Q1209991$A4146462-9DB9-4459-ADEE-63FEEF50AE25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"074909181d0111a45358b746ff15e97cbc132dcf","datavalue":{"value":{"text":"An execution mechanism for nondeterministic, state-oriented programs based on a chart parser","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209991$8C7D3953-028D-430A-AB08-6A1E6DF2263C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb2bd8afb1e1577d1bacba93d653a865e6a2bc6f","datavalue":{"value":"0783.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$FC2C860C-6547-4A39-B673-3A53569E4CFF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"21924c25175e44343e1cd79c78861908fc003883","datavalue":{"value":"10.1016/0020-0190(93)90121-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$CBC6BB62-0A0B-47A3-911B-90E129D892A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3099020c37a0c5db3099732ecbeb26ac3d50eaea","datavalue":{"value":{"entity-type":"item","numeric-id":406209,"id":"Q406209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$160C0FB9-071C-46F9-8715-4C20C2A0674C","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":"Q1209991$FD3B2906-B88F-4760-8EC5-C772E0AA74C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-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":"Q1209991$6050E01F-0737-4127-B5FF-F0559C250291","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"30ed8b60ab6d3ecac755aca33ab1541c31bd406a","datavalue":{"value":"The importance of nondeterministic programming languages has long been recognized. There exist, however, only a few execution mechanisms for programs written in such languages. Thus, it may be desirable to study the execution of these programs further.   Several authors have observed that context-free grammars resemble nondeterministic programs with destructive assignments. This suggests the possibility of adapting parsers to obtain execution mechanisms for such programs. We modify a top-down chart parser and derive one of these mechanisms.   Our method has important advantages over a top-down mechanism with backtracking. First, there are programs for which our method terminates, that cause the backtracking method to enter a nonterminating loop. Second, our method has a time complexity that is cubic in the length of the computation. This is a substantial improvement over a top-down mechanism with backtracking, which has a time complexity that is exponential in the length of the computation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209991$F95D0036-DE94-458F-BA2D-F91FDFC52ADF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$61E2F264-8065-4ABA-B01E-75A86B912930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$099897ED-69FD-42D5-9990-62545A5D3E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$8E138F12-2547-4CC7-B05B-F9C978FA75CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b492f281b8f52c724f2bc547e7e570cccf4bd5e0","datavalue":{"value":"68N17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$409A065A-3066-4673-A810-F6AE15BAB7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$7BED5AC3-0D7E-480C-8DC1-BAECE3E9D03A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7398c26e553155b483fbbaf44cb2c0e0060e551d","datavalue":{"value":"168865","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$9AB0D131-1058-4638-B148-8ADC3B4AC1F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddda5dcd351c8143f72228f5c8ad7cb170e527d3","datavalue":{"value":"state-oriented programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209991$572BDE3B-4524-4463-970A-F74284465F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2b746efc66121bc1fb497da4ab39b83b5cd2f4c","datavalue":{"value":"program correctness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209991$1E78A21B-9851-4B8B-8E8B-DEC302C99811","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":"Q1209991$E9357414-46E2-4C53-BE5E-8DB2683B260E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6952c964346571cc46d55c2182e9c31b3abf5e35","datavalue":{"value":{"entity-type":"item","numeric-id":1236426,"id":"Q1236426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$4A273E21-25F2-4F14-9910-046EDCD63283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226149966044b48001c0682076573b6d91099455","datavalue":{"value":{"entity-type":"item","numeric-id":4773988,"id":"Q4773988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$23721DD7-7788-45F7-8BD8-99C3A0D85DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe703ad84acbe97ba91280a7535217be8806cf13","datavalue":{"value":{"entity-type":"item","numeric-id":1846738,"id":"Q1846738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$3C5D1790-08B5-4F34-9661-FFFBD253C8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15d8f82c493ecf71b1895a2fbc262dc6af404064","datavalue":{"value":{"entity-type":"item","numeric-id":5532796,"id":"Q5532796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$DCF791DB-01BF-4E40-AD14-FE44DC247FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ff4f0a7b3c0c32e074dafae9e8a1b06e45d04c5","datavalue":{"value":{"entity-type":"item","numeric-id":3779733,"id":"Q3779733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$5F2E68BD-6292-4E23-B9A1-061AB064836E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9a872690aae65aa8cbfced9522c07629e0a8e21","datavalue":{"value":{"entity-type":"item","numeric-id":3862380,"id":"Q3862380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$4BAE7248-C5F6-4F42-A4CA-3432FCFCC294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03dcc815537b517cc71ed958068897d2b199f6d8","datavalue":{"value":{"entity-type":"item","numeric-id":3339245,"id":"Q3339245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209991$A03017B8-41C7-4658-BF5C-5AB6857F1EC3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d1f51f265b625d0c5d5fc755ee3c6d5f24219f52","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90121-o","type":"string"},"datatype":"url"},"type":"statement","id":"Q1209991$8962246F-F7C5-4995-B270-607C6D3FEA37","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"33144441fdb38add1ecb33a1f89b102ee563c18e","datavalue":{"value":"W2042996991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209991$096E64BF-6634-4507-9777-0898D882936C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88aa0cc700972338b0ddb90f96329ef263a426bf","datavalue":{"value":{"entity-type":"item","numeric-id":3779733,"id":"Q3779733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4effdcf191ee39d8a5ffe6d6cdb43a38f473bde","datavalue":{"value":{"amount":"+0.7270037531852722","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":"Q1209991$D3164905-C73B-4479-8E6C-9A81133549DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8574c6b94b645e4096227c6e9da9094218dc5ea5","datavalue":{"value":{"entity-type":"item","numeric-id":4660270,"id":"Q4660270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f9803beee2270def142c2ce1b26a27cd3217280","datavalue":{"value":{"amount":"+0.7165260314941406","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":"Q1209991$713D9E85-028B-412E-85C8-67B63A4D021A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a523b67078d02fd325946f26eeb12acb9b2978e2","datavalue":{"value":{"entity-type":"item","numeric-id":3725570,"id":"Q3725570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"258edb42abcd5c704ecfa64f2740f3047c245b7a","datavalue":{"value":{"amount":"+0.7122961282730103","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":"Q1209991$486DE74C-4789-4830-B606-18601402F664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fb66e3e4d5d74eb20206e543e6172746f2c1f80","datavalue":{"value":{"entity-type":"item","numeric-id":796975,"id":"Q796975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fad547259c3fe3bfc0c0a060acb22c3bf08f5d45","datavalue":{"value":{"amount":"+0.7095698118209839","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":"Q1209991$EEA3E1F4-C63A-4766-B8C5-059C78CFCFB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d33ee4d5a63fb346c6411a87e990b78043dbb4fe","datavalue":{"value":{"entity-type":"item","numeric-id":3489466,"id":"Q3489466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6910f179bc8b87e6430605108e8cd65ce671cb90","datavalue":{"value":{"amount":"+0.7081272006034851","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":"Q1209991$0D2E4097-3CE2-49E2-85F3-448523E5DA03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An execution mechanism for nondeterministic, state-oriented programs based on a chart parser","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_execution_mechanism_for_nondeterministic,_state-oriented_programs_based_on_a_chart_parser"}}}}}