The complexity of model-checking tail-recursive higher-order fixpoint logic

DOI10.3233/FI-2021-1996MaRDI QIDQ4989164zbMATH OpenFDO

Authors Florian Bruse, Martin Lange, Etienne Lozes

Publication date 21 May 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2021-1996

Mathematics Subject Classification ID

Logic in computer science (03B70) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Space-efficient fragments of higher-order fixpoint logic
• The Complexity of Model Checking Higher-Order Fixpoint Logic
• Mathematical Foundations of Computer Science 2005
• CONCUR 2004 - Concurrency Theory
• Model Checking the First-Order Fragment of Higher-Order Fixpoint Logic

Cites work

• Alternation
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Capturing bisimulation-invariant complexity classes with higher-order modal fixpoint logic
• CONCUR 2004 - Concurrency Theory
• scientific article; zbMATH DE number 1048047 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Model Checking the First-Order Fragment of Higher-Order Fixpoint Logic
• On the Computational Complexity of Algorithms
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• Propositional dynamic logic of context-free programs and fixpoint logic with chop
• Relationships between nondeterministic and deterministic tape complexities
• Results on the propositional \(\mu\)-calculus
• Space-efficient fragments of higher-order fixpoint logic
• The Complexity of Model Checking Higher-Order Fixpoint Logic
• The expressive power of higher-order types or, life without CONS
• Uniform inevitability is tree automaton ineffable

Cited in

(7)

• Alternating parity Krivine automata
• Capturing bisimulation-invariant complexity classes with higher-order modal fixpoint logic
• Model Checking the First-Order Fragment of Higher-Order Fixpoint Logic
• The Complexity of Model Checking Higher-Order Fixpoint Logic
• CONCUR 2004 - Concurrency Theory
• Mathematical Foundations of Computer Science 2005
• Separating the expressive power of propositional dynamic and modal fixpoint logics

This page was built for publication: The complexity of model-checking tail-recursive higher-order fixpoint logic

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