Lower bounds for the size of deterministic unranked tree automata
type: Item
instance of: scholarly article
title: Lower bounds for the size of deterministic unranked tree automata
zbMATH Open document ID: 1257.68099
author: Xiaoxue Piao
author: Kai Salomaa
published in: Theoretical Computer Science
publication date: 2012-10-11T00:00:00Z
review text: In an unranked tree a node labeled with a given input symbol may have any number of children. Therefore, the state transitions of a finite bottom-up automaton operating on such trees are defined by regular string languages over the state alphabet. These languages, one for each input symbol, are defined by finite automata. Hence the tree automaton has two kinds of states, the vertical states used in the bottom-up main computation and the horizontal states used for computing the vertical state transitions. Both the vertical and the horizontal behavior may be either deterministic or nondeterministic. In general, the deterministic bottom-up tree automaton with the minimal total number of states recognizing a given regular unranked tree language is not unique, and finding lower bounds for the total number of states is hard. In this paper the authors give an improved lower bound for the size blow-up resulting from the determinization of a nondeterministic unranked tree automaton.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6093045
zbMATH Keywords: tree automata
zbMATH Keywords: unranked trees
zbMATH Keywords: tree languages
zbMATH Keywords: state complexity
zbMATH Keywords: determinization
zbMATH Keywords: lower bounds
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.03.043
OpenAlex ID: W2081745941
cites work: Intersection and union of regular languages and state complexity
cites work: Fundamentals of Computation Theory
cites work: Estimation of state complexity of combined operations
cites work: A lower bound technique for the size of nondeterministic finite automata
cites work: Q5422234
cites work: NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: Q4337605
cites work: DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
cites work: On the minimization of XML schemas and tree automata for unranked trees
cites work: Typechecking for XML transformers
cites work: On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
cites work: Unambiguous Finite Automata over a Unary Alphabet
cites work: Transformations Between Different Models of Unranked Bottom-Up Tree Automata
cites work: State Trade-Offs in Unranked Tree Automata
cites work: State Complexity of Kleene-Star Operations on Trees
cites work: Q4714446
cites work: Undecidability of the State Complexity of Composed Regular Operations
cites work: Automata for XML -- a survey
cites work: A Second Course in Formal Languages and Automata Theory
cites work: On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
DOI: 10.1016/J.TCS.2012.03.043
description: scientific article; zbMATH DE number 6093045