A bounding quantifier

DOI10.1007/978-3-540-30124-0_7MaRDI QIDQ5311284zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk

Publication date 22 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100120

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• A unified approach to boundedness properties in MSO
• Monadic second order finite satisfiability and unbounded tree-width
• Weak \(\text{MSO}+U\) over infinite trees
• Weak MSO+U with path quantifiers over infinite trees
• Capturing MSO with one quantifier

Cited in

(24)

• Beyond -regular languages: T-regular expressions and their automata and logic counterparts
• Parameterized linear temporal logics meet costs: still not costlier than LTL
• Contribution of Warsaw logicians to computational logic
• The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic
• Delay games with WMSO+U winning conditions
• Recursion schemes and the WMSO+U logic
• Beyond BS-regular languages: T-regular expressions and counter-check automata
• Trading bounds for memory in games with counters
• Baire category quantifier in monadic second order logic
• Monadic Second Order Logic with Measure and Category Quantifiers
• Parameterized linear temporal logics meet costs: still not costlier than LTL
• Recursion schemes, the MSO logic, and the \textsf{U} quantifier
• Undecidability of a weak version of MSO+U
• A unified approach to boundedness properties in MSO
• Weak MSO with the unbounding quantifier
• Cost Automata, Safe Schemes, and Downward Closures
• Positive First-order Logic on Words and Graphs
• An interval temporal logic characterization of extended \(\omega\)-regular languages
• Cost automata, safe schemes, and downward closures
• Extending the WMSO+U logic with quantification over tuples
• Constraint automata on infinite data trees: from \(\mathrm{CTL}(\mathbb{Z})/\mathrm{CTL}^*(\mathbb{Z})\) to decision procedures
• Constraint automata on infinite data trees: from CTL\((\mathbb{Z})\text{CTL}^*(\mathbb{Z})\) to decision procedures
• Church synthesis on register automata over linearly ordered data domains
• On the expansion of monadic second-order logic with Cantor-Bendixson rank and order type predicates

This page was built for publication: A bounding quantifier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311284)