Weak MSO with the unbounding quantifier

DOI10.1007/s00224-010-9279-2zbMath1227.03051OpenAlexW2010137316MaRDI 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 logicfinite automata\(\omega\)-regular languagesacceptance by automatalogical expressibility

Mathematics Subject Classification ID

Related Items (15)

Metric propositional neighborhood logic with an equivalence relation ⋮ Delay Games with WMSO$$+$$U Winning Conditions ⋮ Recursion Schemes and the WMSO+U Logic ⋮ Parameterized linear temporal logics meet costs: still not costlier than LTL ⋮ Finite-state strategies in delay games ⋮ The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic ⋮ Delay Games with WMSO+U Winning Conditions ⋮ Church synthesis on register automata over linearly ordered data domains ⋮ An interval temporal logic characterization of extended \(\omega\)-regular languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts ⋮ Unnamed Item ⋮ Wadge-Wagner hierarchies

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

This page was built for publication: Weak MSO with the unbounding quantifier