𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity of weak acceptance conditions in tree automata

✍ Scribed by Jakub Neumann; Andrzej Szepietowski; Igor Walukiewicz

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
98 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Weak acceptance conditions for automata on infinite words or trees are defined in terms of the set of states that appear in the run. This is in contrast with, more usual, strong conditions that are defined in terms of states appearing infinitely often on the run. Weak conditions appear in the context of model-checking and translations of logical formalisms to automata. We study the complexity of the emptiness problem for tree automata with weak conditions. We also study the translations between automata with weak and strong conditions.

πŸ“œ SIMILAR VOLUMES

Minimal separating sets for acceptance c
Minimal separating sets for acceptance conditions in Muller Automata
✍ Helmut Lescow; Jens VΓΆge πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 115 KB

For a Muller automaton only a subset of its states is needed to decide whether a run is accepting or not. The set I of the inÿnitely often visited states can be replaced by the intersection I ∩ W with a ÿxed set W of states, provided W is large enough to distinguish between accepting and non-accepti

Logical Complexity of Some Classes of Tr
Logical Complexity of Some Classes of Tree Languages Generated by Multiple-Tree-Automata
✍ Wojciech Buszkowski πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 515 KB

LOGICAL COMPLEXITY O F SOME CLASSES O F TREE LANGUAGES GENERATED BY MULTIPLE-TREE-AUTOMATA by WOJCIECH BUSZKOWSKI in Poznaii (Poland) 0. Introduction. Preliminary terminology and notation Multiple-tree-automata (MTAs) correspond to the kind of grammars called Lindenmayer systems with tables (cf. ROZ

A kleene-like characterization of langua
A kleene-like characterization of languages accepted by systolic tree automata
✍ E. Fachini; A. Monti πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 686 KB

We present a Kleen-like characterization of the class of languages accepted by systolic binary tree automata, L(SBTA). This characterization uses union, intersection, restricted concatenation, restricted concatenation closure, and finite substitution closure. The restrictions we impose on the operat