Tree-walking automata do not recognize all regular languages

被引：19

作者：

Bojanczyk, Mikolaj ^{[1
]}

Colcombet, Thomas ^{[2
]}

机构：

[1] Warsaw Univ, Inst Informat, PL-02097 Warsaw, Poland

[2] CNRS, IRISA, F-35042 Rennes, France

来源：

SIAM JOURNAL ON COMPUTING | 2008年 / 38卷 / 02期

关键词：

tree automata; formal languages; tree-walking automata;

D O I：

10.1137/050645427

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Tree-walking automata are a natural sequential model for recognizing tree languages. It is well known that every tree language recognized by a tree-walking automaton is regular. We show that the converse does not hold.

引用

页码：658 / 701

页数：44

共 12 条

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

AHO, AV ;

ULLMAN, JD .

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

[2] Tree-walking automata cannot be determinized [J].

Bojanczyk, M ;

Colcombet, T .

THEORETICAL COMPUTER SCIENCE, 2006, 350 (2-3) :164-173

[3]

Bojañczyk M, 2003, LECT NOTES COMPUT SC, V2914, P62

[4]

COMON H, 2002, TREE AUTOMATA TECHNI

[5] TREE-TRANSDUCERS, L SYSTEMS, AND 2-WAY MACHINES [J].

ENGELFRIET, J ;

ROZENBERG, G ;

SLUTZKI, G .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 20 (02) :150-202

[6]

Engelfriet J., 1999, Acta Cybernetica, V14, P51

[7]

ENGELFRIET J, 2007, LOG METHODS COMPUT S, V3

[8]

Engelfriet J., 1999, JEWELS FOREVER CONTR, P72

[9] PARALLEL AND 2-WAY AUTOMATA ON DIRECTED ORDERED ACYCLIC GRAPHS [J].

KAMIMURA, T ;

SLUTZKI, G .

INFORMATION AND CONTROL, 1981, 49 (01) :10-51

[10] Complementing deterministic tree-walking automata [J].

Muscholl, A ;

Samuelides, M ;

Segoufin, L .

INFORMATION PROCESSING LETTERS, 2006, 99 (01) :33-39

← 1 2 →