Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/961
Title: Minimizing Tree Automata for Unranked Trees
Authors: MARTENS, Wim 
Niehren, J.
Issue Date: 2005
Publisher: Springer
Source: DATABASE PROGRAMMING LANGUAGES. p. 232-246
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE
Series/Report no.: 3774
Abstract: Automata for unranked trees form a foundation for XML schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. We start with the unranked tree automata (UTAs) that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal UTAs in that class are not unique and that minimization is np-hard. We then study more recent automata classes that do allow for polynomial time minimization. Among those, we show that bottom-up deterministic stepwise tree automata yield the most succinct representations.
Document URI: http://hdl.handle.net/1942/961
ISBN: 3-540-30951-9
ISSN: 0302-9743
DOI: 10.1007/11601524_15
ISI #: 000235803000015
Category: A1
Type: Journal Contribution
Validations: ecoom 2007
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
minimizing.pdf480.12 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

12
checked on Sep 4, 2020

WEB OF SCIENCETM
Citations

10
checked on May 13, 2022

Page view(s)

48
checked on May 18, 2022

Download(s)

142
checked on May 18, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.