Jump to content

Regular tree grammar: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
m General fixes, typo(s) fixed: straight-forward → straightforward, decidible → decidable using AWB (9936)
OAbot (talk | contribs)
Bots
441,761 edits
m Open access bot: hdl updated in citation with #oabot.
 
(33 intermediate revisions by 20 users not shown)
Line 1: Line 1:
In [[theoretical computer science]] and [[formal language theory]], a '''regular tree grammar''' ('''RTG''')<ref>{{cite paper | id = {{citeseerx|10.1.1.164.5484}} | title = Regular tree grammars as a formalism for scope underspecification }}</ref> is a [[formal grammar]] that describes a set of [[Tree (graph theory)|directed trees]], or [[term (logic)|terms]]. A [[regular grammar|regular word grammar]] can be seen as a special kind of regular tree grammar, describing a set of single-[[Path (graph theory)|path]] trees.
In [[theoretical computer science]] and [[formal language theory]], a '''regular tree grammar''' is a [[formal grammar]] that describes a set of [[Tree (graph theory)|directed trees]], or [[term (logic)|terms]].<ref>{{cite CiteSeerX | citeseerx=10.1.1.164.5484 | title = Regular tree grammars as a formalism for scope underspecification }}</ref> A [[regular grammar|regular word grammar]] can be seen as a special kind of regular tree grammar, describing a set of single-[[Path (graph theory)|path]] trees.


==Definition==
==Definition==
Line 9: Line 9:
where
where


* ''N'' is a set of nonterminals,
* ''N'' is a finite set of nonterminals,
* Σ is a ranked alphabet (i.e., an alphabet whose symbols have an associated [[arity]]) disjoint from ''N'',
* Σ is a [[ranked alphabet]] (i.e., an alphabet whose symbols have an associated [[arity]]) disjoint from ''N'',
* ''Z'' is the starting nonterminal, with ''Z'' ∈ ''N'', and
* ''Z'' is the starting nonterminal, with {{math|''Z'' ∈ ''N''}}, and
* ''P'' is a set of productions of the form ''A'' → ''t'', with ''A'' ∈ ''N'', and ''t'' ∈ ''T''<sub>Σ</sub>(''N''), where ''T''<sub>Σ</sub>(''N'') is the associated [[term algebra]], i.e. the set of all trees composed from symbols in Σ ∪ ''N'' according to their arities, where nonterminals are considered nullary.
* ''P'' is a finite set of productions of the form ''A'' → ''t'', with {{math|''A'' ∈ ''N''}}, and {{math|''t'' ∈ ''T''<sub>Σ</sub>(''N'')}}, where ''T''<sub>Σ</sub>(''N'') is the associated [[term algebra]], i.e. the set of all trees composed from symbols in {{math|Σ ∪ ''N''}} according to their arities, where nonterminals are considered nullary.


==Derivation of trees==
==Derivation of trees==
Line 19: Line 19:
More formally, the relation ⇒<sub>''G''</sub> on the set ''T''<sub>Σ</sub>(''N'') is defined as follows:
More formally, the relation ⇒<sub>''G''</sub> on the set ''T''<sub>Σ</sub>(''N'') is defined as follows:


A tree ''t''<sub>1</sub>∈ ''T''<sub>Σ</sub>(''N'') can be '''derived in a single step''' into a tree ''t''<sub>2</sub> ∈ ''T''<sub>Σ</sub>(''N'')
A tree {{math|''t''<sub>1</sub>∈ ''T''<sub>Σ</sub>(''N'')}} can be '''derived in a single step''' into a tree {{math|''t''<sub>2</sub> ∈ ''T''<sub>Σ</sub>(''N'')}}
(in short: ''t''<sub>1</sub> ⇒<sub>''G''</sub> ''t''<sub>2</sub>), if there is a context ''S'' and a production (''A''→''t'') ∈ ''P'' such that:
(in short: ''t''<sub>1</sub> ⇒<sub>''G''</sub> ''t''<sub>2</sub>), if there is a context ''S'' and a production {{math|(''A''→''t'') ∈ ''P''}} such that:


* ''t''<sub>1</sub> = ''S''[''A''], and
* ''t''<sub>1</sub> = ''S''[''A''], and
Line 27: Line 27:
Here, a ''context'' means a tree with exactly one hole in it; if ''S'' is such a context, ''S''[''t''] denotes the result of filling the tree ''t'' into the hole of ''S''.
Here, a ''context'' means a tree with exactly one hole in it; if ''S'' is such a context, ''S''[''t''] denotes the result of filling the tree ''t'' into the hole of ''S''.


The tree language generated by ''G'' is the language ''L''(''G'') = { ''t'' ∈ ''T''<sub>Σ</sub> | ''Z'' ⇒<sub>''G''*</sub> ''t'' }.
The tree language generated by ''G'' is the language {{math|1=''L''(''G'') = {{mset| ''t'' ∈ ''T''<sub>Σ</sub> | ''Z'' ⇒<sub>''G''*</sub> ''t'' }}}}.


Here, ''T''<sub>Σ</sub> denotes the set of all trees composed from symbols of Σ, while ⇒<sub>''G''*</sub> denotes successive applications of ⇒<sub>''G''</sub>.
Here, ''T''<sub>Σ</sub> denotes the set of all trees composed from symbols of Σ, while ⇒<sub>''G''*</sub> denotes successive applications of ⇒<sub>''G''</sub>.
Line 57: Line 57:


The tree language generated by ''G''<sub>1</sub> is the set of all finite lists of boolean values, that is, ''L''(''G''<sub>1</sub>) happens to equal ''T''<sub>Σ1</sub>.
The tree language generated by ''G''<sub>1</sub> is the set of all finite lists of boolean values, that is, ''L''(''G''<sub>1</sub>) happens to equal ''T''<sub>Σ1</sub>.
The grammar ''G''<sub>1</sub> corresponds to the algebraic data type declarations
The grammar ''G''<sub>1</sub> corresponds to the algebraic data type declarations (in the [[Standard ML#Algebraic datatypes|Standard ML]] programming language):

<!--abusing "ocaml" scheme for standard ML syntax as long as no highlighting is supported for the latter-->
<source lang="ocaml">
<syntaxhighlight lang="sml">
datatype Bool
datatype Bool
= false
= false
Line 66: Line 66:
= nil
= nil
| cons of Bool * BList
| cons of Bool * BList
</syntaxhighlight>
</source>
in the [[Standard ML#Algebraic datatypes and pattern matching|Standard ML]] programming language: every member of ''L''(''G''<sub>1</sub>) corresponds to a Standard-ML value of type BList.
Every member of ''L''(''G''<sub>1</sub>) corresponds to a Standard-ML value of type BList.


For another example, let ''G''<sub>2</sub> = (''N''<sub>1</sub>,Σ<sub>1</sub>,''BList1'',''P''<sub>1</sub> ∪ ''P''<sub>2</sub>), using the nonterminal set and the alphabet from above, but extending the production set by ''P''<sub>2</sub>, consisting of the following productions:
For another example, let {{math|1=''G''<sub>2</sub> = (''N''<sub>1</sub>, Σ<sub>1</sub>, ''BList''{{sub|1}}, ''P''<sub>1</sub> ∪ ''P''<sub>2</sub>)}}, using the nonterminal set and the alphabet from above, but extending the production set by ''P''<sub>2</sub>, consisting of the following productions:
* ''BList1'' → ''cons''(''true'',''BList'')
* ''BList''{{sub|1}} → ''cons''(''true'',''BList'')
* ''BList1'' → ''cons''(''false'',''BList1'')
* ''BList''{{sub|1}} → ''cons''(''false'',''BList''{{sub|1}})
The language ''L''(''G''<sub>2</sub>) is the set of all finite lists of boolean values that contain ''true'' at least once. The set ''L''(''G''<sub>2</sub>) has no '''datatype''' counterpart in Standard ML, nor in any other functional language.
The language ''L''(''G''<sub>2</sub>) is the set of all finite lists of boolean values that contain ''true'' at least once. The set ''L''(''G''<sub>2</sub>) has no '''datatype''' counterpart in Standard ML, nor in any other functional language.
It is a proper subset of ''L''(''G''<sub>1</sub>).
It is a proper subset of ''L''(''G''<sub>1</sub>).
The above example term happens to be in ''L''(''G''<sub>2</sub>), too, as the following derivation shows:
The above example term happens to be in ''L''(''G''<sub>2</sub>), too, as the following derivation shows:


''BList1''
''BList''{{sub|1}}
⇒ ''cons''(''false'',''BList1'')
⇒ ''cons''(''false'',''BList''{{sub|1}})
⇒ ''cons''(''false'',''cons''(''true'',''BList''))
⇒ ''cons''(''false'',''cons''(''true'',''BList''))
⇒ ''cons''(''false'',''cons''(''true'',''nil'')).
⇒ ''cons''(''false'',''cons''(''true'',''nil'')).
Line 83: Line 83:
==Language properties==
==Language properties==


If ''L''<sub>1</sub>, ''L''<sub>2</sub> both are regular tree languages, then the tree sets ''L''<sub>1</sub> ∩ ''L''<sub>2</sub>, ''L''<sub>1</sub> ∪ ''L''<sub>2</sub>, and ''L''<sub>1</sub> \ ''L''<sub>2</sub> are also regular tree languages, and it is decidable whether ''L''<sub>1</sub> ⊆ ''L''<sub>2</sub>, and whether ''L''<sub>1</sub> = ''L''<sub>2</sub>.
If ''L''<sub>1</sub>, ''L''<sub>2</sub> both are regular tree languages, then the tree sets {{math|''L''<sub>1</sub> ∩ ''L''<sub>2</sub>, ''L''<sub>1</sub> ∪ ''L''<sub>2</sub>}}, and ''L''<sub>1</sub> \ ''L''<sub>2</sub> are also regular tree languages, and it is decidable whether {{math|''L''<sub>1</sub> ⊆ ''L''<sub>2</sub>}}, and whether ''L''<sub>1</sub> = ''L''<sub>2</sub>.


==Alternative characterizations and relation to other formal languages==
==Alternative characterizations and relation to other formal languages==
Rajeev Alur and Parthasarathy Madhusudan<ref name=Alur2004>{{cite doi|10.1145/1007352.1007390}} Sect.4, Theorem 5,</ref><ref name=Alur2009>{{cite doi|10.1145/1516512.1516518}} Sect.7</ref> related a subclass of regular binary tree languages to [[nested word]]s and [[visibly pushdown language]]s.


⚫
*Regular tree grammars are a generalization of [[Regular grammar|regular word grammars]].
The regular tree languages are also<ref name=Comon>Comon et al, [http://www.grappa.univ-lille3.fr/tata Tree Automata Techniques and Applications], 1997</ref> the languages recognized by bottom-up [[Tree automaton|tree automata]] and nondeterministic top-down tree automata.
*The regular tree languages are also the languages recognized by bottom-up [[Tree automaton|tree automata]] and nondeterministic top-down tree automata.<ref name=Comon>{{cite web |last1=Comon |first1=Hubert |last2=Dauchet |first2=Max |last3=Gilleron |first3=Remi |last4=Löding |first4=Christof |last5=Jacquemard |first5=Florent |last6=Lugiez |first6=Denis |last7=Tison |first7=Sophie |last8=Tommasi |first8=Marc |date=12 October 2007 |title=Tree Automata Techniques and Applications |url=http://www.grappa.univ-lille3.fr/tata |access-date=25 January 2016 }}</ref>
*Rajeev Alur and Parthasarathy Madhusudan related a subclass of regular binary tree languages to [[nested word]]s and [[visibly pushdown language]]s.<ref name=Alur2004>{{Cite book| doi = 10.1145/1007352.1007390 | last1 = Alur | first1 = R. | last2 = Madhusudan| isbn = 978-1581138528 | first2 = P.| chapter = Visibly pushdown languages | title = Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 | pages = 202–211| year = 2004 | s2cid = 7473479 | chapter-url = http://www.cis.upenn.edu/~alur/Stoc04.pdf| url = https://repository.upenn.edu/cgi/viewcontent.cgi?article=1174&context=cis_papers }} Sect.4, Theorem 5,</ref><ref name=Alur2009>{{Cite journal | doi = 10.1145/1516512.1516518| last1 = Alur | first1 = R. | last2 = Madhusudan | first2 = P. | title = Adding nesting structure to words | journal = Journal of the ACM | volume = 56 | issue = 3 | pages = 1–43 | year = 2009 | url = http://www.cis.upenn.edu/~alur/Jacm09.pdf| citeseerx = 10.1.1.145.9971| s2cid = 768006 }} Sect.7</ref>


==Applications==
⚫
Regular tree grammars are a generalization of [[Regular grammar|regular word grammars]].
⚫
Applications of regular tree grammars include:
⚫
* [[Code generation (compiler)#Major tasks in code generation|Instruction selection]] in compiler code generation<ref>{{cite conference|first1=Helmut|last1=Emmelmann|title=Code Selection by Regularly Controlled Term Rewriting|book-title=Code Generation - Concepts, Tools, Techniques|publisher=Springer|series=Workshops in Computing|pages=3–29|year=1991}}</ref>
⚫
* A [[decision procedure]] for the [[first-order logic]] [[Theory (mathematical logic)|theory]] of formulas over [[First-order logic#Equality and its axioms|equality]] (=) and [[Set (mathematics)#Membership|set membership]] (∈) as the only [[First-order logic#Non-logical symbols|predicates]]<ref>{{cite conference|first1=Hubert|last1=Comon|title=Equational Formulas in Order-Sorted Algebras|book-title=Proc. ICALP|year=1990}}</ref>
⚫
* Solving [[Constraint satisfaction problem#Decision problems|constraints]] about mathematical sets<ref>{{cite conference|first1=R.|last1=Gilleron|first2=S.|last2=Tison|first3=M.|last3=Tommasi|title=Solving Systems of Set Constraints using Tree Automata|book-title=10th Annual Symposium on Theoretical Aspects of Computer Science|publisher=Springer|series=LNCS|volume=665|pages=505–514|year=1993}}</ref>
⚫
* The set of all truths expressible in [[first-order logic]] about a finite algebra (which is always a regular tree language)<ref>{{cite conference|first1=Jochen|last1=Burghardt|title=Axiomatization of Finite Algebras|book-title=Advances in Artificial Intelligence|publisher=Springer|series=LNAI|volume=2479|pages=222–234|isbn=3-540-44185-9|arxiv=1403.7347|year=2002|bibcode=2014arXiv1403.7347B}}</ref>
* Graph-search <ref>{{cite conference|first1=Smoly |last1=Ziv-Ukelson|title=Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human–viral Infection Patterns|year=2016|publisher=J. of Comp. Bio.}} [https://www.liebertpub.com/doi/full/10.1089/cmb.2015.0168]</ref>


==See also==
==See also==
* [[Set constraint]] – a generalization of regular tree grammars
* [[Tree-adjoining grammar]]
* [[Tree-adjoining grammar]]
⚫
* A book devoted to tree grammars: {{cite book|first1=Maurice|last1=Nivat|first2=Andreas|last2=Podelski|title=Tree Automata and Languages|series=Studies in Computer Science and Artificial Intelligence|volume=10|publisher=North-Holland|year=1992}}
⚫
* Regular tree grammars were already described in 1968 by:
⚫
**{{cite journal|first1=W.S.|last1=Brainerd|title=The Minimalization of Tree Automata|journal=Information and Control|volume=13|pages=484–491|year=1968}}
⚫
** {{cite journal|first1=J.W.|last1=Thatcher|first2=J.B.|last2=Wright|title=Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic|journal=Mathematical Systems Theory|volume=2|number=1|year=1968}}
⚫
* Applications of regular tree grammars include:
⚫
** [[Code generation (compiler)#Major tasks in code generation|Instruction selection]] in compiler code generation:{{cite conference|first1=Helmut|last1=Emmelmann|title=Code Selection by Regularly Controlled Term Rewriting|booktitle=Code Generation - Concepts, Tools, Techniques|publisher=Springer|series=Workshops in Computing|pages=3–29|year=1991}}
⚫
** A [[decision procedure]] for the [[first-order logic]] [[Theory (mathematical logic)|theory]] of formulas over [[First-order logic#Equality and its axioms|equality]] (=) and [[Set (mathematics)#Membership|set membership]] (∈) as the only [[First-order logic#Non-logical symbols|predicates]]: {{cite conference|first1=Hubert|last1=Comon|title=Equational Formulas in Order-Sorted Algebras|booktitle=Proc. ICALP|year=1990}}
⚫
** Solving [[Constraint satisfaction problem#Decision problems|constraints]] about mathematical sets: {{cite conference|first1=R.|last1=Gilleron|first2=S.|last2=Tison|first3=M.|last3=Tommasi|title=Solving Systems of Set Constraints using Tree Automata|booktitle=10th Annual Symposium on Theoretical Aspects of Computer Science|publisher=Springer|series=LNCS|volume=665|pages=505–514|year=1993}}
⚫
** The set of all truths expressible in [[first-order logic]] about a finite algebra is always a regular tree language: {{cite conference|first1=Jochen|last1=Burghardt|title=Axiomatization of Finite Algebras|booktitle=Advances in Artificial Intelligence|publisher=Springer|series=LNAI|volume=2479|pages=222–234|isbn=3-540-44185-9|url=http://user.cs.tu-berlin.de/~jochen/ki02.pdf|year=2002}}
⚫
* Algorithms on regular tree grammars are discussed from an efficiency-oriented view in: {{cite conference|first1=A.|last1=Aiken|first2=B.|last2=Murphy|title=Implementing Regular Tree Expressions|booktitle=ACM Conference on Functional Programming Languages and Computer Architecture|pages=427–447|year=1991|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3766}}
⚫
* Given a mapping from trees to weights, Knuth's generalization of [[Dijkstra's algorithm|Dijkstra's shortest-path algorithm]] can be applied to a regular tree grammar to compute for each nonterminal the minimum weight of a derivable tree: {{cite journal|first1=D.E.|last1=Knuth|title=A Generalization of Dijkstra's Algorithm|journal=Information Processing Letters|volume=6|number=1|pages=1–5|year=1977}}. Based on this information, it is straightforward to enumerate its language in increasing weight order. In particular, any nonterminal with infinite minimum weight produces the empty language.
⚫
* Regular tree automata have been generalized to admit equality tests between sibling nodes in trees: {{cite conference|first1=B.|last1=Bogaert|first2=Sophie|last2=Tison|title=Equality and Disequality Constraints on Direct Subterms in Tree Automata|booktitle=Proc. 9th STACS|publisher=Springer|series=LNCS|volume=577|pages=161–172|year=1992}}
⚫
* Allowing equality tests between deeper nodes leads to undecidibility: {{citation|first1=M.|last1=Tommasi|title=Automates d'Arbres avec Tests d'Égalités entre Cousins Germains|publisher=LIFL-IT|year=1991}}


==References==
==References==
{{reflist}}
{{reflist}}


==External links==
==Further reading==
⚫
* Regular tree grammars were already described in 1968 by:
* [http://tata.gforge.inria.fr/ Tree Automata Techniques and Applications]
⚫
**{{Cite journal | last1 = Brainerd | first1 = W.S. | year = 1968 | title = The Minimalization of Tree Automata | journal = Information and Control | volume = 13 | issue = 5| pages = 484–491 | doi = 10.1016/s0019-9958(68)90917-0 | doi-access = free | hdl = 10945/40204 | hdl-access = free }}
⚫
** {{cite journal|first1=J.W.|last1=Thatcher|first2=J.B.|last2=Wright|title=Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic|journal=Mathematical Systems Theory|volume=2|pages=57–81|number=1|year=1968|doi=10.1007/BF01691346|s2cid=31513761}}
⚫
* A book devoted to tree grammars is: {{cite book|first1=Maurice|last1=Nivat|first2=Andreas|last2=Podelski|title=Tree Automata and Languages|series=Studies in Computer Science and Artificial Intelligence|volume=10|publisher=North-Holland|year=1992}}
⚫
* Algorithms on regular tree grammars are discussed from an efficiency-oriented view in: {{cite conference|first1=A.|last1=Aiken|first2=B.|last2=Murphy|title=Implementing Regular Tree Expressions|book-title=ACM Conference on Functional Programming Languages and Computer Architecture|pages=427–447|year=1991|citeseerx=10.1.1.39.3766}}
⚫
* Given a mapping from trees to weights, [[Donald Knuth]]'s generalization of [[Dijkstra's algorithm|Dijkstra's shortest-path algorithm]] can be applied to a regular tree grammar to compute for each nonterminal the minimum weight of a derivable tree. Based on this information, it is straightforward to enumerate its language in increasing weight order. In particular, any nonterminal with infinite minimum weight produces the empty language. See: {{cite journal|first1=D.E.|last1=Knuth|title=A Generalization of Dijkstra's Algorithm|journal=Information Processing Letters|volume=6|number=1|pages=1–5|year=1977|doi=10.1016/0020-0190(77)90002-3}}
⚫
* Regular tree automata have been generalized to admit equality tests between sibling nodes in trees. See: {{cite conference|first1=B.|last1=Bogaert|first2=Sophie|last2=Tison|title=Equality and Disequality Constraints on Direct Subterms in Tree Automata|book-title=Proc. 9th STACS|publisher=Springer|series=LNCS|volume=577|pages=161–172|year=1992}}
⚫
* Allowing equality tests between deeper nodes leads to undecidability. See: {{cite book|first1=M.|last1=Tommasi|title=Automates d'Arbres avec Tests d'Égalités entre Cousins Germains|publisher=LIFL-IT|year=1991}}

{{Formal languages and grammars |state=collapsed}}


[[Category:Formal languages]]
[[Category:Formal languages]]

Latest revision as of 03:57, 15 July 2024

In theoretical computer science and formal language theory, a regular tree grammar is a formal grammar that describes a set of directed trees, or terms.[1] A regular word grammar can be seen as a special kind of regular tree grammar, describing a set of single-path trees.

Definition

[edit]

A regular tree grammar G is defined by the tuple

G = (N, Σ, Z, P),

where

  • N is a finite set of nonterminals,
  • Σ is a ranked alphabet (i.e., an alphabet whose symbols have an associated arity) disjoint from N,
  • Z is the starting nonterminal, with Z ∈ N, and
  • P is a finite set of productions of the form A → t, with A ∈ N, and t ∈ TΣ(N), where TΣ(N) is the associated term algebra, i.e. the set of all trees composed from symbols in Σ ∪ N according to their arities, where nonterminals are considered nullary.

Derivation of trees

[edit]

The grammar G implicitly defines a set of trees: any tree that can be derived from Z using the rule set P is said to be described by G. This set of trees is known as the language of G. More formally, the relation ⇒G on the set TΣ(N) is defined as follows:

A tree t1∈ TΣ(N) can be derived in a single step into a tree t2 ∈ TΣ(N) (in short: t1 ⇒G t2), if there is a context S and a production (A→t) ∈ P such that:

  • t1 = S[A], and
  • t2 = S[t].

Here, a context means a tree with exactly one hole in it; if S is such a context, S[t] denotes the result of filling the tree t into the hole of S.

The tree language generated by G is the language L(G) = { t ∈ TΣ | Z ⇒G* t }.

Here, TΣ denotes the set of all trees composed from symbols of Σ, while ⇒G* denotes successive applications of ⇒G.

A language generated by some regular tree grammar is called a regular tree language.

Examples

[edit]
Example derivation tree from G1 in linear (upper left table) and graphical (main picture) notation

Let G1 = (N1,Σ1,Z1,P1), where

  • N1 = {Bool, BList } is our set of nonterminals,
  • Σ1 = { true, false, nil, cons(.,.) } is our ranked alphabet, arities indicated by dummy arguments (i.e. the symbol cons has arity 2),
  • Z1 = BList is our starting nonterminal, and
  • the set P1 consists of the following productions:
    • Bool → false
    • Bool → true
    • BList → nil
    • BList → cons(Bool,BList)

An example derivation from the grammar G1 is

BList ⇒ cons(Bool,BList) ⇒ cons(false,cons(Bool,BList)) ⇒ cons(false,cons(true,nil)).

The image shows the corresponding derivation tree; it is a tree of trees (main picture), whereas a derivation tree in word grammars is a tree of strings (upper left table).

The tree language generated by G1 is the set of all finite lists of boolean values, that is, L(G1) happens to equal TΣ1. The grammar G1 corresponds to the algebraic data type declarations (in the Standard ML programming language): 

  datatype Bool
    = false
    | true
  datatype BList
    = nil
    | cons of Bool * BList

Every member of L(G1) corresponds to a Standard-ML value of type BList.

For another example, let G2 = (N1, Σ1, BList1, P1 ∪ P2), using the nonterminal set and the alphabet from above, but extending the production set by P2, consisting of the following productions:

  • BList1 → cons(true,BList)
  • BList1 → cons(false,BList1)

The language L(G2) is the set of all finite lists of boolean values that contain true at least once. The set L(G2) has no datatype counterpart in Standard ML, nor in any other functional language. It is a proper subset of L(G1). The above example term happens to be in L(G2), too, as the following derivation shows:

BList1 ⇒ cons(false,BList1) ⇒ cons(false,cons(true,BList)) ⇒ cons(false,cons(true,nil)).

Language properties

[edit]

If L1, L2 both are regular tree languages, then the tree sets L1 ∩ L2, L1 ∪ L2, and L1 \ L2 are also regular tree languages, and it is decidable whether L1 ⊆ L2, and whether L1 = L2.

Alternative characterizations and relation to other formal languages

[edit]

Applications

[edit]

Applications of regular tree grammars include:

See also

[edit]

References

[edit]
  1. ^ "Regular tree grammars as a formalism for scope underspecification". CiteSeerX 10.1.1.164.5484.
  2. ^ Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 October 2007). "Tree Automata Techniques and Applications". Retrieved 25 January 2016.
  3. ^ Alur, R.; Madhusudan, P. (2004). "Visibly pushdown languages" (PDF). Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04. pp. 202–211. doi:10.1145/1007352.1007390. ISBN 978-1581138528. S2CID 7473479. Sect.4, Theorem 5,
  4. ^ Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words" (PDF). Journal of the ACM. 56 (3): 1–43. CiteSeerX 10.1.1.145.9971. doi:10.1145/1516512.1516518. S2CID 768006. Sect.7
  5. ^ Emmelmann, Helmut (1991). "Code Selection by Regularly Controlled Term Rewriting". Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29.
  6. ^ Comon, Hubert (1990). "Equational Formulas in Order-Sorted Algebras". Proc. ICALP.
  7. ^ Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Solving Systems of Set Constraints using Tree Automata". 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. Vol. 665. Springer. pp. 505–514.
  8. ^ Burghardt, Jochen (2002). "Axiomatization of Finite Algebras". Advances in Artificial Intelligence. LNAI. Vol. 2479. Springer. pp. 222–234. arXiv:1403.7347. Bibcode:2014arXiv1403.7347B. ISBN 3-540-44185-9.
  9. ^ Ziv-Ukelson, Smoly (2016). Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human–viral Infection Patterns. J. of Comp. Bio. [1]

Further reading

[edit]
  • Regular tree grammars were already described in 1968 by:
  • A book devoted to tree grammars is: Nivat, Maurice; Podelski, Andreas (1992). Tree Automata and Languages. Studies in Computer Science and Artificial Intelligence. Vol. 10. North-Holland.
  • Algorithms on regular tree grammars are discussed from an efficiency-oriented view in: Aiken, A.; Murphy, B. (1991). "Implementing Regular Tree Expressions". ACM Conference on Functional Programming Languages and Computer Architecture. pp. 427–447. CiteSeerX 10.1.1.39.3766.
  • Given a mapping from trees to weights, Donald Knuth's generalization of Dijkstra's shortest-path algorithm can be applied to a regular tree grammar to compute for each nonterminal the minimum weight of a derivable tree. Based on this information, it is straightforward to enumerate its language in increasing weight order. In particular, any nonterminal with infinite minimum weight produces the empty language. See: Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3.
  • Regular tree automata have been generalized to admit equality tests between sibling nodes in trees. See: Bogaert, B.; Tison, Sophie (1992). "Equality and Disequality Constraints on Direct Subterms in Tree Automata". Proc. 9th STACS. LNCS. Vol. 577. Springer. pp. 161–172.
  • Allowing equality tests between deeper nodes leads to undecidability. See: Tommasi, M. (1991). Automates d'Arbres avec Tests d'Égalités entre Cousins Germains. LIFL-IT.
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Regular_tree_grammar&oldid=1234587157"