Weak MSO with the unbounding quantifier

DOI10.1007/s00224-010-9279-2zbMath1227.03051MaRDI QIDQ537919

Mikołaj Bojańczyk

Publication date: 23 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1834/

zbMATH Keywords

monadic second-order logic; finite automata; \(\omega\)-regular languages; acceptance by automata; logical expressibility

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

Related Items

Unnamed Item, Unnamed Item, Metric propositional neighborhood logic with an equivalence relation, Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts, Wadge-Wagner hierarchies, Finite-state strategies in delay games, Parameterized linear temporal logics meet costs: still not costlier than LTL, Delay Games with WMSO+U Winning Conditions, Unnamed Item, Delay Games with WMSO$$+$$U Winning Conditions, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Factorization forests for infinite words and applications to countable scattered linear orderings
• A syntactic congruence for rational \(\omega\)-languages
• Algorithms for determining relative star height and star height
• Weighted automata and weighted logics
• On the definition of a family of automata
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• The recursive sets in certain monadic second order fragments of arithmetic
• Computer Science Logic
• Distance desert automata and the star height problem