|
|||||
|
|
Deciding determinism of caterpillar expressions |
|
| Authors: | Kai Salomaa Sheng Yu Jinfeng Zan |
| Affiliation: | 1. School of Computing, Queen’s University, Kingston, Ontario K7L 3N6, Canada;2. Department of Computer Science, University of Western Ontario, London, Ontario N6A 5B7, Canada |
| Abstract: | Caterpillar expressions have been introduced by Brüggemann-Klein and Wood for applications in markup languages. Caterpillar expressions provide a convenient formalism for specifying the operation of tree-walking automata on unranked trees. Here we give a formal definition of determinism of caterpillar expressions that is based on the language of instruction sequences defined by the expression. We show that determinism of caterpillar expressions can be decided in polynomial time. |
| Keywords: | Regular expressions Tree-walking automata Determinism Decidability |
| 本文献已被 ScienceDirect 等数据库收录！ | |