Abstract | ||
---|---|---|
The theory of 2-structures [see, e.g., Ehrenfeucht and Rozenberg (1990) ] provides a convenient framework for investigating various mathematical structures encountered in computer science. This paper investigates a subclass of 2-structures, called T-structures , which turned out to be important in the investigation of basic properties of 2-structures [see Ehrenfeucht and Rozenberg (1992) ]. We prove that T-structures are a natural generalization of linear orders; in particular, we prove that a T-structure can be represented by two linear orders. Based on this result, the notion of a text is introduced which generalizes the notion of a word as used in formal language theory. A text may be seen as a word with a “structure” spanned on it; this structure may be a tree, but it may also be more general than a tree. Basic properties of the class of texts corresponding to trees are investigated. |
Year | DOI | Venue |
---|---|---|
1993 | 10.1016/0304-3975(93)90323-L | Theor. Comput. Sci. |
DocType | Volume | Issue |
Journal | 116 | 2 |
ISSN | Citations | PageRank |
Theoretical Computer Science | 9 | 0.74 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
A. Ehrenfeucht | 1 | 1823 | 497.83 |
G. Rozenberg | 2 | 43 | 4.35 |