Jump to content

User:Stgrue/sandbox/Interpreted regular tree grammar

From Wikipedia, the free encyclopedia

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]