User:Stgrue/sandbox/Interpreted regular tree grammar

In computational linguistics and formal language theory, an interpreted regular tree grammar (IRTG) is a regular tree grammar (RTG) extended by one or more interpretations. These interpretations map the trees generated by the underlying RTG onto other objects, e.g. strings or graphs; consequently, the language described by an IRTG is the set of all objects that can be generated in this fashion.

The idea underlying IRTGs is similar to that of synchronous context-free grammars: A single common set of rules acts as ... For example, an IRTG might have two interpretations, which map trees onto strings and graphs, respectively. This way,

IRTGs generalize a number of grammar formalisms, such as context-free grammar, tree-adjoining grammar, and hyperedge replacement grammar. General algorithms

Definitions

A $\Sigma$-interpretation is a pair ${\mathcal {I}}=(h,{\mathcal {A}})$, where ${\mathcal {A}}$ is a $\Delta$-algebra, and $h:T_{\Sigma }\rightarrow T_{\Delta }$ is a tree homomorphism.

An IRTG $\mathbb {G}$ is then defined as a tuple $\mathbb {G} =({\mathcal {G}},{\mathcal {I}}_{1},...,{\mathcal {I}}_{n})$, where $\mathbb {G}$ is a regular tree grammar over the ranked alphabet $\Sigma$, and ${\mathcal {I}}_{1},...,{\mathcal {I}}_{n}$ are $\Sigma$-interpretations.

The language $L(\mathbb {G} )$ then consists of

$L(\mathbb {G} )=\{\langle \rangle \}$

Parsing

Three-step process: Regular decomposition, inverse homomorphism, intersection with RTG.