RAIRO - Theoretical Informatics and Applications · 1991 · 48 citations · 4 references
ComputingComputer ScienceAlgorithmsNatural Language ProcessingParallel ComputingSyntactic AnalysisSyntax AnalysisAcyclic HypergraphsBottom-up Rewrite SystemsRewrite SystemsRewriting SystemsTerm RewritingTerm Rewriting SystemsTermination Of Term Rewriting Systems
Jungles are acyclic hypergraphs which represent sets of terms such that common subterms can be shared. Term rewrite rules are translated into jungle valuation rules which implement parallel term rewriting steps. By using additional hypergraph rules which "fold" equal subterms, even non-left-linear term rewriting Systems can be implemented. As a side effect, these folding rules can speed up the valuation process considerably. It is shown that terminating term rewriting Systems resuit in terminating jungle valuation Systems which are capable to normalize every term. Moreover, confluent and terminating term rewriting Systems give rise to confluent and terminating jungle valuation Systems, provided that the "garbage" produced by the valuation steps is ignored.
4
Proving termination with multiset orderings
Nachum Dershowitz, Zohar Manna · Communications of the ACM · 1979 · 540 citations · Full text
Jean Claude Raoult · Theoretical Computer Science · 1984 · 96 citations
Computation on graph-like expressions
John Staples · Theoretical Computer Science · 1980 · 43 citations
Graph grammars and operational semantics
Peter Padawitz · Theoretical Computer Science · 1982 · 17 citations