
arXiv: 0804.3065
Tree automata with one memory have been introduced in 2001. They generalize both pushdown (word) automata and the tree automata with constraints of equality between brothers of Bogaert and Tison. Though it has a decidable emptiness problem, the main weakness of this model is its lack of good closure properties. We propose a generalization of the visibly pushdown automata of Alur and Madhusudan to a family of tree recognizers which carry along their (bottom-up) computation an auxiliary unbounded memory with a tree structure (instead of a symbol stack). In other words, these recognizers, called Visibly Tree Automata with Memory (VTAM) define a subclass of tree automata with one memory enjoying Boolean closure properties. We show in particular that they can be determinized and the problems like emptiness, membership, inclusion and universality are decidable for VTAM. Moreover, we propose several extensions of VTAM whose transitions may be constrained by different kinds of tests between memories and also constraints a la Bogaert and Tison comparing brother subtrees in the tree in input. We show that some of these classes of constrained VTAM keep the good closure and decidability properties, and we demonstrate their expressiveness with relevant examples of tree languages.
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], i.2.3, Alternating automata, i.2.2, Logic, Pushdown Automata, F.1.1; F.1.2; I.2.2; I.2.3, Tree automata, computer science - logic in computer science, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.3: Deduction and Theorem Proving, First-order theorem proving, resource-bounded), Symbolic constraints, push-down, finite, ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.0: Automata (e.g., I.2.2, I.2.3, f.1.1, BC1-199, f.1.2, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.2: Automatic Programming/I.2.2.4: Program verification, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], QA75.5-76.95, 004, Logic in Computer Science (cs.LO), Electronic computers. Computer science, F.1.2, F.1.1
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], i.2.3, Alternating automata, i.2.2, Logic, Pushdown Automata, F.1.1; F.1.2; I.2.2; I.2.3, Tree automata, computer science - logic in computer science, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.3: Deduction and Theorem Proving, First-order theorem proving, resource-bounded), Symbolic constraints, push-down, finite, ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.0: Automata (e.g., I.2.2, I.2.3, f.1.1, BC1-199, f.1.2, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.2: Automatic Programming/I.2.2.4: Program verification, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], QA75.5-76.95, 004, Logic in Computer Science (cs.LO), Electronic computers. Computer science, F.1.2, F.1.1
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
