Term graph

Add links
Source: Wikipedia, the free encyclopedia.

A term graph is a representation of an expression in a formal language as a generalized graph whose vertices are terms[clarify].[1] Term graphs are a more powerful form of representation than expression trees because they can represent not only common subexpressions (i.e. they can take the structure of a directed acyclic graph) but also cyclic/recursive subexpressions (cyclic digraphs).

Abstract syntax trees cannot represent shared subexpressions since each tree node can only have one parent; this simplicity comes at the cost of efficiency due to redundant duplicate computations of identical terms. For this reason term graphs are often used as an

intermediate language
at a subsequent compilation stage to abstract syntax tree construction via parsing.

The phrase "

term graph rewriting" is often used when discussing graph rewriting methods for transforming expressions in formal languages.[2]
Considered from the point of view of graph grammars, term graphs are not regular graphs, but hypergraphs where an n-ary word will have a particular subgraph in first place, another in second place, and so on, a distinction that does not exist in the usual undirected graphs studied in graph theory.

Term graphs are a prominent topic in programming language research since term graph rewriting rules can formally expressing a compiler's operational semantics. Term graphs are also used as abstract machines capable of modelling chemical and biological computations as well as graphical calculi such as concurrency models. Term graphs can perform automated verification and logical programming since they are well-suited to representing quantified statements in first order logic. Symbolic programming software is another application for term graphs, which are capable of representing and performing computation with abstract algebraic structures such as groups, fields and rings.

The TERMGRAPH conference [3] focuses entirely on research into term graph rewriting and its applications.

Term graphs are also used in type inference, where the graph structure aids in implementing type unification.[4]

See also

References

  1. ISBN 9789810228842.{{cite book}}: CS1 maint: multiple names: authors list (link
    )
  2. ISBN 978-3-540-17945-0
    .
  3. ^ "TERMGRAPH 2013".
  4. doi:10.1145/62678.62701
Stub icon

This formal methods-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Term_graph&oldid=1268543950"