Institutional Repository
| subtyping algorithm of regular tree grammars with disjoint production rules | |
| Chen Lei; Chen Haiming | |
| 2010 | |
| Conference Name | 7th International Colloquium on Theoretical Aspects of Computing, ICTAC 2010 |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 45-59 |
| Conference Date | September |
| Conference Place | Natal, Brazil |
| Publish Place | Germany |
| Publisher | THEORETICAL ASPECTS OF COMPUTING |
| ISSN | 3029743 |
| ISBN | 3642148077 |
| Department | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China |
| English Abstract | Most type systems of statically typed XML processing languages are implemented based on regular expression types, where subtyping reduces to checking inclusion between tree automata, which is not efficient enough. The paper proposes the regular tree grammars with disjoint production rules and presents a subtyping method which is based on checking inclusion between regular expressions. The commonly used XML schema languages such as DTDs and XML Schemas can be described by the restricted grammars. The method works in a bottom-up way on the structures of type expressions. According to the regular expressions used in XML schema languages, different inclusion algorithms can be applied to this method. Experiments show the effectiveness of our method. © 2010 Springer-Verlag. |
| Keyword | Algorithms Trees (Mathematics) |
| Sponsorship | Univ Fed Rio Grande Norte, Univ York |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8922 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Chen Lei,Chen Haiming. subtyping algorithm of regular tree grammars with disjoint production rules[C]. Germany:THEORETICAL ASPECTS OF COMPUTING,2010:45-59. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| subtyping algorithm （325KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment