<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>
Tree equivalence is a relation among polyadic recursion schemes. This relation is broad enough to be interesting: equivalent schemes may not be obviously equivalent and may still differ in computationally important ways. We show that this relation is also narrow enough to imply input-output equivalence.Is tree equivalence decidable? We assign context-free grammars to recursion schemes in such a way that schemes are tree equivalent iff their grammars generate the same language. Known results on LL(k) grammars then imply that tree equivalence is decidable for a class of schemes which includes the monadic recursion schemes without constants. Some important nonmonadic schemes are also included.
Computational Theory and Mathematics, Computer Networks and Communications, Applied Mathematics, General topics in the theory of software, Formal languages and automata, Theoretical Computer Science
Computational Theory and Mathematics, Computer Networks and Communications, Applied Mathematics, General topics in the theory of software, Formal languages and automata, Theoretical Computer Science
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). | 30 | |
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 1% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |