Operational State Complexity of Subtree-Free Regular Tree Languages

Sang Ki Ko; Hae Sung Eom; Yo Sub Han

doi:10.1142/S0129054116500246

Operational State Complexity of Subtree-Free Regular Tree Languages

Sang Ki Ko
, Hae Sung Eom
, Yo Sub Han

Department of Artificial Intelligence

Yonsei University

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.

Original language	English
Pages (from-to)	705-724
Number of pages	20
Journal	International Journal of Foundations of Computer Science
Volume	27
Issue number	6
DOIs	https://doi.org/10.1142/S0129054116500246
State	Published - 1 Sep 2016

Keywords

Deterministic ranked tree automata
state complexity
subtree-free regular tree languages

Access to Document

10.1142/S0129054116500246

Cite this

@article{785fa8069c9849408de37d2c9e261569,

title = "Operational State Complexity of Subtree-Free Regular Tree Languages",

abstract = "We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.",

keywords = "Deterministic ranked tree automata, state complexity, subtree-free regular tree languages",

author = "Ko, \{Sang Ki\} and Eom, \{Hae Sung\} and Han, \{Yo Sub\}",

note = "Publisher Copyright: {\textcopyright} 2016 World Scientific Publishing Company.",

year = "2016",

month = sep,

day = "1",

doi = "10.1142/S0129054116500246",

language = "English",

volume = "27",

pages = "705--724",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "6",

}

TY - JOUR

T1 - Operational State Complexity of Subtree-Free Regular Tree Languages

AU - Ko, Sang Ki

AU - Eom, Hae Sung

AU - Han, Yo Sub

PY - 2016/9/1

Y1 - 2016/9/1

N2 - We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.

AB - We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.

KW - Deterministic ranked tree automata

KW - state complexity

KW - subtree-free regular tree languages

UR - https://www.scopus.com/pages/publications/84995537934

U2 - 10.1142/S0129054116500246

DO - 10.1142/S0129054116500246

M3 - Article

AN - SCOPUS:84995537934

SN - 0129-0541

VL - 27

SP - 705

EP - 724

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 6

ER -

Operational State Complexity of Subtree-Free Regular Tree Languages

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this