
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.
Specification and verification (program logics, model checking, etc.), Analysis of algorithms and problem complexity, program correctness, state-oriented programs, Theory of compilers and interpreters, Formal languages and automata, Logic programming
Specification and verification (program logics, model checking, etc.), Analysis of algorithms and problem complexity, program correctness, state-oriented programs, Theory of compilers and interpreters, Formal languages and automata, Logic programming
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
