Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy
For a tree language L, a finite set 2 of regular Sigma-path languages, and a set S of 2-prefix constrained linear monadic term rewriting rules over Sigma, the position cutting descendant of L for S is the set S*(up arrow) (L) of trees reachable from a tree in L by rewriting in S by position cutting...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2018
|
| Sorozat: | THEORETICAL COMPUTER SCIENCE
732 |
| doi: | 10.1016/j.tcs.2018.04.026 |
| mtmt: | 3389344 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/13934 |
| Tartalmi kivonat: | For a tree language L, a finite set 2 of regular Sigma-path languages, and a set S of 2-prefix constrained linear monadic term rewriting rules over Sigma, the position cutting descendant of L for S is the set S*(up arrow) (L) of trees reachable from a tree in L by rewriting in S by position cutting strategy. If L is recognizable, then S*(up arrow) (L) is recognizable as well. Moreover, if S is finite, then we can construct a tree automaton recognizing S*(up arrow) (L). For a recognizable tree language L and a finite set 2 of regular Sigma-path languages, we study the set D-z,D-up arrow(L) of position cutting descendants of L for all sets of 2-prefix constrained linear monadic term rewriting rules over Sigma. We show that D-z,D-up arrow(L) is finite, and that if L is given by a tree automaton A and each element of 2 is given by an automaton, then we can construct a set {R-1, . . . , R-k} of Z-prefix constrained linear monadic term rewriting systems over Sigma such that D-z,D-up arrow (L) = {R-1*(up arrow)(L),...,R-k*(up arrow) (L)}. (C) 2018 Elsevier B.V. All rights reserved. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 60-72 |
| ISSN: | 0304-3975 |