Transformations Between Different Types of Unranked Bottom-Up Tree Automata
We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represent...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2010-08-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1008.1658v1 |
| _version_ | 1811262803468615680 |
|---|---|
| author | Xiaoxue Piao Kai Salomaa |
| author_facet | Xiaoxue Piao Kai Salomaa |
| author_sort | Xiaoxue Piao |
| collection | DOAJ |
| description | We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, Lect. Notes Comput. Sci. 3623, pp. 68-79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata. |
| first_indexed | 2024-04-12T19:32:06Z |
| format | Article |
| id | doaj.art-824533db339b41218a15ee8697b11b57 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-12T19:32:06Z |
| publishDate | 2010-08-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-824533db339b41218a15ee8697b11b572022-12-22T03:19:18ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802010-08-0131Proc. DCFS 201015916810.4204/EPTCS.31.18Transformations Between Different Types of Unranked Bottom-Up Tree AutomataXiaoxue PiaoKai SalomaaWe consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, Lect. Notes Comput. Sci. 3623, pp. 68-79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.http://arxiv.org/pdf/1008.1658v1 |
| spellingShingle | Xiaoxue Piao Kai Salomaa Transformations Between Different Types of Unranked Bottom-Up Tree Automata Electronic Proceedings in Theoretical Computer Science |
| title | Transformations Between Different Types of Unranked Bottom-Up Tree Automata |
| title_full | Transformations Between Different Types of Unranked Bottom-Up Tree Automata |
| title_fullStr | Transformations Between Different Types of Unranked Bottom-Up Tree Automata |
| title_full_unstemmed | Transformations Between Different Types of Unranked Bottom-Up Tree Automata |
| title_short | Transformations Between Different Types of Unranked Bottom-Up Tree Automata |
| title_sort | transformations between different types of unranked bottom up tree automata |
| url | http://arxiv.org/pdf/1008.1658v1 |
| work_keys_str_mv | AT xiaoxuepiao transformationsbetweendifferenttypesofunrankedbottomuptreeautomata AT kaisalomaa transformationsbetweendifferenttypesofunrankedbottomuptreeautomata |