Tree Automata with Global Constraints for Infinite Trees

被引：0

作者：

Landwehr, Patrick ^{[1
]}

Loeding, Christof ^{[1
]}

机构：

[1] Rhein Westfal TH Aachen, Aachen, Germany

来源：

36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019) | 2019年

关键词：

Tree automata; infinite trees; global constraints;

D O I：

10.4230/LIPIcs.STACS.2019.47

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study an extension of tree automata on infinite trees with global equality and disequality constraints. These constraints can enforce that all subtrees for which in the accepting run a state q is reached (at the root of that subtree) are identical, or that these trees differ from the subtrees at which a state q' is reached. We consider the closure properties of this model and its decision problems. While the emptiness problem for the general model remains open, we show the decidability of the emptiness problem for the case that the given automaton only uses equality constraints.

引用

页数：15

共 26 条

[1] [Anonymous], 1990, HDB THEORETICAL COMP
[2] [Anonymous], 2007, LOGIC AUTOMATA
[3] Baader F, 2012, LECT NOTES COMPUT SC, V7180, P107, DOI 10.1007/978-3-642-28717-6_11
[4] The Emptiness Problem for Tree Automata with Global Constraints
Barguno, Luis
Creus, Carles
Godoy, Guillem
Jacquemard, Florent
Vacher, Camille
[J]. 25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010), 2010, : 263 - 272
[5] Bernholtz O., 1994, Computer Aided Verification. 6th International Conference, CAV '94. Proceedings, P142
[6] BOGAERT B, 1992, LECT NOTES COMPUT SC, V577, P161
[7] Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings
Carayol, Arnaud
Loeding, Christof
Serre, Olivier
[J]. PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), 2016, : 227 - 236
[8] TQL: a query language for sernistructured data based on the ambient logic
Cardelli, L
Ghelli, G
[J]. MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2004, 14 (03) : 285 - 327
[9] Filiot E, 2008, LECT NOTES COMPUT SC, V5257, P314, DOI 10.1007/978-3-540-85780-8_25
[10] Filiot E, 2007, LECT NOTES COMPUT SC, V4646, P130

← 1 2 3 →