Bottom-Up Tree Automata with Term Constraints

被引：4
作者：
Reuss, Andreas [1 ]
Seidl, Helmut [1 ]
机构：
[1] Tech Univ Munich, Inst Informat 12, D-85748 Garching, Germany
来源：
LOGIC FOR PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND REASONING | 2010年 / 6397卷
关键词：
D O I：
10.1007/978-3-642-16242-8_41
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We introduce bottom-up tree automata with equality and disequality term constraints. These constraints are more expressive than the equality and disequality constraints between brothers introduced by Bogaert and Tison in 1992. Our new class of automata is still closed under Boolean operations. Moreover, we show that for tree automata with term constraints not only membership but also emptiness is decidable. This contrasts with the undecidability of emptiness for automata with arbitrary equality constraints between subterms identified by paths as shown in 1981 by Mongy.
引用
收藏
页码：581 / 593
页数：13
相关论文
共 50 条
  • [21] Linear deterministic multi bottom-up tree transducers
    Fülöp, Z
    Kühnemann, A
    Vogler, H
    THEORETICAL COMPUTER SCIENCE, 2005, 347 (1-2) : 276 - 287
  • [22] Bottom-Up Tree Evaluation in Tree-Based Genetic Programming
    Li, Geng
    Zeng, Xiao-Jun
    ADVANCES IN SWARM INTELLIGENCE, PT 1, PROCEEDINGS, 2010, 6145 : 513 - 522
  • [23] The Bottom-Up Position Tree Automaton and the Father Automaton
    Attou, Samira
    Mignot, Ludovic
    Ziadi, Djelloul
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2020, 31 (08) : 1051 - 1068
  • [24] COMPOSITION OF TOP-DOWN AND BOTTOM-UP TREE TRANSDUCTIONS
    BAKER, BS
    INFORMATION AND CONTROL, 1979, 41 (02): : 186 - 213
  • [25] The Bottom-Up Position Tree Automaton and Its Compact Version
    Attou, Samira
    Mignot, Ludovic
    Ziadi, Djelloul
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2018, 2018, 10977 : 59 - 70
  • [26] EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS
    Friese, Sylvia
    Seidl, Helmut
    Maneth, Sebastian
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2011, 22 (07) : 1607 - 1623
  • [27] On the String Translations Produced by Multi Bottom-Up Tree Transducers
    Gildea, Daniel
    COMPUTATIONAL LINGUISTICS, 2012, 38 (03) : 673 - 693
  • [28] MORE EFFICIENT BOTTOM-UP TREE PATTERN-MATCHING
    CAI, J
    PAIGE, R
    TARJAN, R
    LECTURE NOTES IN COMPUTER SCIENCE, 1990, 431 : 72 - 86
  • [29] Bottom-Up Generative Modeling of Tree-Structured Data
    Bacciu, Davide
    Micheli, Alessio
    Sperduti, Alessandro
    NEURAL INFORMATION PROCESSING: THEORY AND ALGORITHMS, PT I, 2010, 6443 : 660 - +
  • [30] BOTTOM-UP AND TOP-DOWN TREE TRANSFORMATIONS - COMPARISON
    ENGELFRIET, J
    MATHEMATICAL SYSTEMS THEORY, 1975, 9 (03): : 198 - 231
12345