Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875478 | Theoretical Computer Science | 2018 | 13 Pages |
Abstract
For a tree language L, a finite set Z of regular Σ-path languages, and a set S of Z-prefix constrained linear monadic term rewriting rules over Σ, the position cutting descendant of L for S is the set Sââ(L) of trees reachable from a tree in L by rewriting in S by position cutting strategy. If L is recognizable, then Sââ(L) is recognizable as well. Moreover, if S is finite, then we can construct a tree automaton recognizing Sââ(L). For a recognizable tree language L and a finite set Z of regular Σ-path languages, we study the set DZ,â(L) of position cutting descendants of L for all sets of Z-prefix constrained linear monadic term rewriting rules over Σ. We show that DZ,â(L) is finite, and that if L is given by a tree automaton A and each element of Z is given by an automaton, then we can construct a set {R1,â¦,Rk} of Z-prefix constrained linear monadic term rewriting systems over Σ such that DZ,â(L)={R1ââ(L),â¦,Rkââ(L)}.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sándor Vágvölgyi,