Skip to Main content Skip to Navigation
Conference papers

Weak MSO with the Unbounding Quantifier

Abstract : A new class of languages of infinite words is introduced, called the max-regular languages, extending the class of ω-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier). Effective translations between the logic and automata are given.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00359061
Contributor : Publications Loria <>
Submitted on : Thursday, February 5, 2009 - 2:33:49 PM
Last modification on : Monday, June 8, 2020 - 10:54:03 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:55:40 PM

Files

bojanczyk_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359061, version 1
  • ARXIV : 0902.1042

Collections

Citation

Mikolaj Bojanczyk. Weak MSO with the Unbounding Quantifier. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.159-170. ⟨inria-00359061⟩

Share

Metrics

Record views

114

Files downloads

412