Complexity of weak acceptance conditions in tree automata.
type: Item
instance of: scholarly article
title: Complexity of weak acceptance conditions in tree automata.
zbMATH Open document ID: 1042.68068
DOI: 10.1016/S0020-0190(02)00285-5
author: Jakub Neumann
author: Andrzej Szepietowski
author: Igor Walukiewicz
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1856473
zbMATH Keywords: Formal languages
zbMATH Keywords: Computational complexity
zbMATH Keywords: Tree automata
zbMATH Keywords: Weak conditions
zbMATH Keywords: Emptiness problem
MaRDI profile type: Publication
cites work: Q3739111
cites work: Number of quantifiers is better than number of tape cells
cites work: An automata-theoretic approach to branching-time model checking
cites work: Q4055589
cites work: Hierarchies of weak automata and weak monadic formulas
cites work: FINITE STATE PROCESSES, Z-TEMPORAL LOGIC AND THE MONADIC THEORY OF THE INTEGERS
cites work: Q3746905
cites work: Q4385530
cites work: Q4714446
description: scientific article; zbMATH DE number 1856473