Complexity of weak acceptance conditions in tree automata. (Q1853134)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1856473
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Complexity of weak acceptance conditions in tree automata. |
scientific article; zbMATH DE number 1856473 |
Statements
Complexity of weak acceptance conditions in tree automata. (English)
0 references
21 January 2003
0 references
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.
0 references
Formal languages
0 references
Computational complexity
0 references
Tree automata
0 references
Weak conditions
0 references
Emptiness problem
0 references
0.8518587946891785
0 references
