Complexity of weak acceptance conditions in tree automata.

DOI10.1016/S0020-0190(02)00285-5zbMath1042.68068MaRDI QIDQ1853134

Andrzej Szepietowski, Jakub Neumann, Igor Walukiewicz

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Computational complexityFormal languagesTree automataEmptiness problemWeak conditions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Sofic tree-shifts ⋮ Answering regular path queries mediated by unrestricted \(\mathcal{SQ}\) ontologies

Cites Work

• Hierarchies of weak automata and weak monadic formulas
• Number of quantifiers is better than number of tape cells
• FINITE STATE PROCESSES, Z-TEMPORAL LOGIC AND THE MONADIC THEORY OF THE INTEGERS
• An automata-theoretic approach to branching-time model checking
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of weak acceptance conditions in tree automata.