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

edit

A  -interpretation is a pair  , where   is a  -algebra, and   is a tree homomorphism.

An IRTG   is then defined as a tuple  , where   is a regular tree grammar over the ranked alphabet  , and   are  -interpretations.

The language   then consists of

 


Example

edit

Parsing

edit

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


References

edit