State complexity of Kleene-star operations on regulat tree languages

Han, Yo-Sub: State complexity of Kleene-star operations on regulat tree languages. Acta cybernetica, (22) 2. pp. 403-422. (2015)

[img] Cikk, tanulmány, mű
actacyb_22_2_2015_11.pdf

Download (472kB)

Abstract

The concatenation of trees can be defined either as a sequential or a parallel operation, and the corresponding iterated operation gives an extension of Kleene-star to tree languages. Since the sequential tree concatenation is not associative, we get two essentially different iterated sequential concatenation operations that we call the bottom-up star and top-down star operation, respectively. We establish that the worst-case state complexity of bottom-up star is (n + 3/2) · 2 n−1. The bound differs by an order of magnitude from the corresponding result for string languages. The state complexity of top-down star is similar as in the string case. We consider also the state complexity of the star of the concatenation of a regular tree language with the set of all trees.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2015
Volume: 22
Number: 2
Page Range: pp. 403-422
ISSN: 0324-721X
Language: angol
DOI: https://doi.org/10.14232/actacyb.22.2.2015.11
Uncontrolled Keywords: Matematikai nyelvészet
Additional Information: Bibliogr.: p. 421-422.
Date Deposited: 2016. Oct. 17. 10:36
Last Modified: 2018. Jun. 06. 18:50
URI: http://acta.bibl.u-szeged.hu/id/eprint/36211

Actions (login required)

View Item View Item