<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>
handle: 11577/2522185
Contents. Abstract, Introduction, 1. Terminology, 2. The relationship between passes and paths, 3. Exponential lower bounds, 4. Upper bounds, 5. Path languages, Conclusion, References.An attribute grammar is pure (left-to-right) multi-pass if a bounded number of left-to-right passes over the derivation tree suffice to compute all its attributes. There is no requirement, as for the usual multi-pass attribute grammars, that all occurrences of the same attribute are computed in the same pass. It is shown that the problem of determining whether an arbitrary attribute grammar is pure multipass, is of inherently exponential time complexity. For fixed k > 0, it can be decided in polynomial time whether an attribute grammar is pure k-pass. The proofs are based on a characterization of pure multi-pass attribute grammars in terms of paths through their dependency graphs. A general result on dependency paths of attribute grammars relates them to (finite-copying) top-down tree transducers. The formal power of k-pass attribute grammars increases with increasing k. Formally, multi-pass attribute grammars are less powerful than arbitrary attribute grammars.
multi-pass attribute grammars, dependency graphs, formal power, Formal languages and automata, top-down tree transducers, Engineering(all)
multi-pass attribute grammars, dependency graphs, formal power, Formal languages and automata, top-down tree transducers, 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). | 17 | |
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). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |