<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
Derivational time and space complexity of context-free grammars is studied. Minimal linear bounds are given for the number of derivation steps needed to derive a word (time complexity) and for the length of the longest sentential form needed in the derivation of a word (space complexity). Coefficients in linear estimations are grammar dependent, for \(\epsilon\)-free grammars they depend on the number of nonterminals and in the case of arbitrary grammars they depend moreover on the number of nullable nonterminals and the length of the longest production. Examples are given to prove the minimality of the given bounds.
number of derivation steps, derivational time and space complexity, minimal grammar dependent bounds, Analysis of algorithms and problem complexity, context-free grammars, minimal linear bounds, Formal languages and automata, Engineering(all)
number of derivation steps, derivational time and space complexity, minimal grammar dependent bounds, Analysis of algorithms and problem complexity, context-free grammars, minimal linear bounds, Formal languages and automata, Engineering(all)
citations 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). | 1 | |
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 |