The Complexity of the Graded µ-Calculus

No abstract is available for this paper.

• Publication year

  2002

• Venue

  CADE

• Publication date

  2002-07-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-45620-1_34
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Expressive Number Restrictions in Description Logics

  2001cited by this paper
• RACER System Description

  2001cited by this paper
• RESULTS ON THE PROPOSITIONAL’p-CALCULUS

  2001cited by this paper
• PSPACE Reasoning for Graded Modal Logics

  2000cited by this paper
• An automata-theoretic approach to branching-time model checking

  2000cited by this paper
• The Complexity of Reasoning with Cardinality Restri tionsand Nominals in Expressive Des ription Logi sStephan

  2000cited by this paper
• Reasoning with Individuals for the Description Logic SHIQ

  2000cited by this paper
• Complexity Results for First-Order Two-Variable Logic with Counting

  2000cited by this paper
• CTL+ is Exponentially more Succinct than CTL

  1999cited by this paper
• Reasoning in Expressive Description Logics with Fixpoints based on Automata on Infinite Trees

  1999cited by this paper
• The two-variable guarded fragment with transitive relations

  1999cited by this paper
• On the Restraining Power of Guards

  1999cited by this paper
• Using an Expressive Description Logic: FaCT or Fiction?

  1998cited by this paper
• Weak alternating automata and tree automata emptiness

  1998cited by this paper
• The Complexity of Concept Languages

  1997cited by this paper
• ω-Languages

  1997cited by this paper
• Two-variable logic with counting is decidable

  1997cited by this paper
• Languages, Automata, and Logic

  1997cited by this paper
• On the Decision Problem for Two-Variable First-Order Logic

  1997cited by this paper
• Efficent Local Model-Checking for Fragments of teh Modal µ-Calculus

  1996cited by this paper
• Monadic Second Order Logic on Tree-Like Structures

  1996cited by this paper
• Simulating Alternating Tree Automata by Nondeterministic Automata: New Results and New Proofs of the Theorems of Rabin, McNaughton and Safra

  1995cited by this paper
• Automata for the Modal mu-Calculus and related Results

  1995cited by this paper
• Counting Objects

  1995cited by this paper
• Boosting the Correspondence between Description Logics and Propositional Dynamic Logics

  1994cited by this paper
• Am empirical analysis of optimization techniques for terminological representation systems

  1994cited by this paper
• Cardinality Restrictions on Concepts

  1994cited by this paper
• Concept Language with Number Restrictions and Fixpoints, and its Relationship with Mu-calculus

  1994cited by this paper
• Terminological Cycles and the Propositional µ-Calculus

  1994cited by this paper
• Terminological Cycles and the Propositional μ-Calculus**This work was supported by a grant from the Deutsche Forschungsgemeinschaft (DFG).

  1994cited by this paper
• On Model-Checking for Fragments of µ-Calculus

  1993cited by this paper
• An Empirical Analysis of Optimization Techniques for Terminological Representation Systems, or Making KRIS Get a Move On

  1992cited by this paper
• Qualifying Number Restrictions in Concept Languages

  1991cited by this paper
• Tree Automata, Mu-Calculus and Determinacy (Extended Abstract)

  1991cited by this paper
• Automata on Infinite Objects

  1991cited by this paper
• The CLASSIC knowledge representation system

  1991cited by this paper
• Structured representation of FMS integrating SI-NETS and high level petri nets

  1990cited by this paper
• An Automata Theoretic Decision Procedure for the Propositional Mu-Calculus

  1989cited by this paper
• Temporal Logic with Fixed Points

  1987cited by this paper
• Alternating Automata on Infinite Trees

  1987cited by this paper
• Temporal Logic in Specification

  1987cited by this paper
• Alternating automata on infinite trees

  1987cited by this paper
• Automata theoretic techniques for modal logics of programs: (Extended abstract)

  1984cited by this paper
• Propositional Dynamic Logic of Regular Programs

  1979cited by this paper
• The Computational Complexity of Provability in Systems of Modal Propositional Logic

  1977cited by this paper
• Log Space Recognition and Translation of Parenthesis Languages

  1977cited by this paper
• In so many possible worlds

  1972cited by this paper
• 理學 : The science

  1946cited by this paper

• Halting Recurrent GNNs and the Graded $\mu$-Calculus

  2025cites this paper
• Graph neural networks and MSO

  2025cites this paper
• A Timed Obstruction Logic for Dynamic Game Models

  2025cites this paper
• Relators and Notions of Simulation Revisited

  2025cites this paper
• The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic

  2025influential citation
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats

  2024cites this paper
• Obstruction Logic: A Strategic Temporal Logic to Reason About Dynamic Game Models

  2023cites this paper
• Generic Model Checking for Modal Fixpoint Logics in COOL-MC

  2023cites this paper
• COOL 2 - A Generic Reasoner for Modal Fixpoint Logics

  2023cites this paper
• COOL 2 - A Generic Reasoner for Modal Fixpoint Logics (System Description)

  2023cites this paper
• A Robust Theory of Series Parallel Graphs

  2023cites this paper
• Coalgebraic Satisfiability Checking for Arithmetic μ-Calculi

  2022cites this paper
• Quasipolynomial Computation of Nested Fixpoints

  2021cites this paper
• On the Description Logic SHOIF Extended with Transitive Closure and (Restricted Forms of) Regular Role Expressions

  2020cites this paper
• On the Decidability of Expressive Description Logics with Transitive Closure and Regular Role Expressions

  2020cites this paper
• Model-checking graded computation-tree logic with finite path semantics

  2020cites this paper
• Game-Based Local Model Checking for the Coalgebraic mu-Calculus

  2019cites this paper
• Computing Nested Fixpoints in Quasipolynomial Time

  2019cites this paper
• Formal Concept Analysis: 15th International Conference, ICFCA 2019, Frankfurt, Germany, June 25–28, 2019, Proceedings

  2019influential citation
• Completeness for μ-calculi: A coalgebraic approach

  2019cites this paper
• Sublogics of a branching time logic of robustness

  2019cites this paper
• Joining Implications in Formal Contexts and Inductive Learning in a Horn Description Logic

  2019cites this paper
• Optimal Satisfiability Checking for Arithmetic μ-Calculi

  2019cites this paper
• Graded modalities in Strategy Logic

  2018cites this paper
• CTL* with graded path modalities

  2018cites this paper
• Graded CTL* over Finite Paths

  2018cites this paper
• Completeness of Flat Coalgebraic Fixpoint Logics

  2018influential citation
• Strategic Reasoning in Game Theory

  2018cites this paper
• Reasoning About Additional Winning Strategies in Two-Player Games

  2017cites this paper
• Quantitative Methods for Similarity in Description Logics

  2017cites this paper
• Graded Strategy Logic: Reasoning about Uniqueness of Nash Equilibria

  2016cites this paper
• NWin: A Tool for Counting Winning Strategies (Demonstration)

  2016cites this paper
• Extended Graded Modalities in Strategy Logic

  2016cites this paper
• Reasoning About Substructures and Games

  2015influential citation
• On CTL* with Graded Path Modalities

  2015cites this paper
• Games with additional winning strategies

  2015cites this paper
• The model checking fingerprints of CTL operators

  2015cites this paper
• Reasoning about CTL ∗ with Graded Path Modalities

  2015influential citation
• On the Counting of Strategies

  2015cites this paper
• Expressiveness and succinctness of a logic of robustness

  2015cites this paper
• On the Model Checking of the Graded μ-calculus on Trees

  2015cites this paper
• On Games in Formal Verification

  2015cites this paper
• Fixpoint Node Selection Query Languages for Trees

  2015cites this paper
• Satisfiability and Model Checking of CTL* with Graded Path Modalities

  2014cites this paper
• Answering regular path queries in expressive Description Logics via alternating tree-automata

  2014cites this paper
• Reasoning About Strategies: On the Model-Checking Problem

  2014cites this paper
• Towards a Description Logic for Program Analysis: Extending ALCQIO with Reachability

  2014cites this paper
• Global Numerical Constraints on Trees

  2014cites this paper
• Substructure Temporal Logic

  2013cites this paper
• Analyse statique de requête pour le Web sémantique

  2012cites this paper
• Beyond Regularity for Presburger Modal Logic

  2012cites this paper
• Automated reasoning on trees with cardinality constraints

  2011cites this paper
• Reasoning About Strategies: On the Model-Checking Problem

  2011cites this paper
• A Tree Logic with Graded Paths and Nominals

  2010cites this paper
• Flat Coalgebraic Fixed Point Logics

  2010influential citation
• A NuSMV Extension for Graded-CTL Model Checking

  2010cites this paper
• Complexity of modal logics with Presburger constraints

  2010cites this paper
• Node Selection Query Languages for Trees

  2010cites this paper
• On the Count of Trees

  2010cites this paper
• Graded Alternating-Time Temporal Logic

  2010cites this paper
• Semantics and Reasoning of Description Logic µALCQO

  2009cites this paper
• EXPTIME Tableaux for the Coalgebraic µ-Calculus

  2009influential citation
• Counting in Trees along Multidirectional Regular Paths

  2009cites this paper
• Graded-CTL: Satisfiability and Symbolic Model Checking

  2009cites this paper
• I ¨ I Infsys R R A R P Q  E D L  A T-a

  2009cites this paper
• Model Checking for Graded CTL

  2009cites this paper
• µ-calculus Pushdown Module Checking with Imperfect State Information

  2008influential citation
• The Complexity of Enriched Mu-Calculi

  2008cites this paper
• Enriched µ-Calculi Module Checking

  2008cites this paper
• CTLModel-Checking with Graded Quantifiers

  2008cites this paper
• How Many Toes Do I Have? Parthood and Number Restrictions in Description Logics

  2008cites this paper
• The Pushdown Module Checking Saga

  2008cites this paper
• Generalizing the Goldblatt-Thomason Theorem and Modal Definability

  2008cites this paper
• Counting in trees

  2008cites this paper
• Enriched µ-Calculus Pushdown Module Checking

  2007cites this paper
• Automata-theoretic techniques for temporal reasoning

  2007cites this paper
• Complexity of modal logic

  2007cites this paper
• Enriched µ-Calculi Module Checking

  2007cites this paper
• State of the Art Survey

  2006cites this paper
• Presburger Modal Logic Is PSPACE-Complete

  2006cites this paper
• The Complexity of Enriched µ-Calculi

  2006influential citation
• Multitree automata that count

  2005cites this paper
• On the undecidability of logics with converse, nominals, recursion and counting

  2004cites this paper
• Counting in Trees for Free

  2004cites this paper
• On the Undecidability of Description and Dynamic Logics with Recursion and Counting

  2003cites this paper
• Description Logics for Ontologies

  2003cites this paper
• XML schema, tree logic and sheaves automata

  2003cites this paper
• Numerical document queries

  2003cites this paper
• Decidability of SHIQ with complex role inclusion axioms

  2003cites this paper
• Automata-Theoretic Decision Procedures for Information Logics

  2002cites this paper
• Description logics: foundations for class-based knowledge representation

  2002cites this paper
• Enriched Μ–calculi Module Checking

  year unknowncites this paper