Complementing deterministic tree-walking automata

被引：22

作者：

Muscholl, A ^{[1
]}

Samuelides, M

Segoufin, L

机构：

[1] Univ Paris 07, LIAFA, Paris, France

[2] Univ Paris 07, CNRS, Paris, France

[3] Univ Paris 11, Orsay, France

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 99卷 / 01期

关键词：

combinatorial problems; formal languages; tree-automata;

D O I：

10.1016/j.ipl.2005.09.017

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider various kinds of deterministic tree-walking automata, with and without pebbles, over ranked and unranked trees. For each such kind of automata we show that there is an equivalent one which never loops. The main consequence of this result is the closure under complementation of the various types of automata we consider with a focus on the number of pebbles used in order to complement the automata. (c) 2006 Elsevier B.V All rights reserved.

引用

页码：33 / 39

页数：7

共 9 条

[1] TRANSLATIONS ON A CONTEXT FREE GRAMMAR [J].

AHO, AV ;

ULLMAN, JD .

INFORMATION AND CONTROL, 1971, 19 (05) :439-+

[2]

BOJANCZYK M, 2004, P INT COLL AUT LANG

[3]

BOJANCZYK M, 2005, P ACM SIGACT S THEOR

[4]

COMON H, 1999, TREE AUTOMATA TECHNI

[5]

ENGELFRIET J, 2005, AUTOMATA NESTED PEBB

[6]

Engelfriet J., 1999, JEWELS FOREVER CONTR, P72

[7] Complexity results for two-way and multi-pebble automata and their logics [J].

Globerman, N ;

Harel, D .

THEORETICAL COMPUTER SCIENCE, 1996, 169 (02) :161-184

[8] Typechecking for XML transformers [J].

Milo, T ;

Suciu, D ;

Vianu, V .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 66 (01) :66-97

[9]

SIPSER M, 1978, IEEE C FDN COMPUTER, P73

← 1 →