An implementation of deterministic tree automata minimization
| Title: | An implementation of deterministic tree automata minimization |
|---|---|
| Authors: | Rafael C. Carrasco; Jan Daciuk; Mikel L. Forcada |
| Contributors: | The Pennsylvania State University CiteSeerX Archives |
| Source: | http://www.dlsi.ua.es/~carrasco/papers/ciaa07.pdf. |
| Collection: | CiteSeerX |
| Description: | A frontier-to-root deterministic finite-state tree automaton (DTA) can be used as a compact data structure to store collections of unranked ordered trees. DTAs are usually sparser than string automata, as most transitions are undefined and therefore, special care must be taken in order to minimize them efficiently. However, it is difficult to find simple and detailed descriptions of the minimization procedure in the published literature. Here, we fully describe a simple implementation of the standard minimization algorithm that needs a time in O(|A | 2), with |A | being the size of the DTA. 1 |
| Document Type: | text |
| File Description: | application/pdf |
| Language: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.5277; http://www.dlsi.ua.es/~carrasco/papers/ciaa07.pdf |
| Availability: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.5277; http://www.dlsi.ua.es/~carrasco/papers/ciaa07.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Accession Number: | edsbas.4DCD1CE5 |
| Database: | BASE |