Closure ordinals for the two-way μ-calculus

Authors
Publication date 2019
Host editors
  • R. Iemhoff
  • M. Moortgat
  • R. de Queiroz
Book title Logic, Language, Information, and Computation
Book subtitle 26th International Workshop, WoLLIC 2019, Utrecht, The Netherlands, July 2-5, 2019 : proceedings
ISBN
  • 9783662595329
ISBN (electronic)
  • 9783662595336
Series Lecture Notes in Computer Science
Event 26th International Workshop on Logic, Language, Information, and Computation
Pages (from-to) 498-515
Publisher Berlin: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract
The closure ordinal of a μ-calculus formula φ(x) is the least ordinal α, if it exists, such that, in any model, the least fixed point of φ(x) can be computed in at most α many steps, by iteration of the meaning function associated with φ(x), starting from the empty set. In this paper we focus on closure ordinals of the two-way modal μ-calculus. Our main technical contribution is the construction of a two-way formula φn with closure ordinal ωn for an arbitrary n∈ω. Building on this construction, as our main result we define a two-way formula φα with closure ordinal α for an arbitrary α<ωω.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-662-59533-6_30
Permalink to this page
Back