Cover Image

The complexity of deciding characteristic formulae in van Glabbeek's branching-time spectrum

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aceto, Luca, Achilleos, Antonis, Chalki, Aggeliki, Ingolfsdottir, Anna
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deciding characteristic formulae: A journey in the branching-time spectrum
by: Aceto, Luca, et al.
Published: (2025)

The Complexity of Deciding Characteristic Formulae Modulo Nested Simulation (extended abstract)
by: Aceto, Luca, et al.
Published: (2025)

Complexity results for modal logic with recursion via translations and tableaux
by: Aceto, Luca, et al.
Published: (2023)

Monitorability for the Modal mu-Calculus over Systems with Data: From Practice to Theory
by: Aceto, Luca, et al.
Published: (2025)

When Are Prime Formulae Characteristic?
by: Aceto, Luca, et al.
Published: (2024)

A unified rule format for bounded nondeterminism in SOS with terms as labels
by: Aceto, Luca, et al.
Published: (2024)

Logical characterisations, rule formats and compositionality for input-output conformance simulation
by: Aceto, Luca, et al.
Published: (2024)

An Undecidability Proof for the Plan Existence Problem
by: Achilleos, Antonis
Published: (2026)

On the specification of modal systems: A comparison of three frameworks
by: Aceto, Luca, et al.
Published: (2024)

Rule Formats for Nominal Process Calculi
by: Aceto, Luca, et al.
Published: (2024)

Centralized vs Decentralized Monitors for Hyperproperties
by: Aceto, Luca, et al.
Published: (2024)

If At First You Don't Succeed: Extended Monitorability through Multiple Executions
by: Achilleos, Antonis, et al.
Published: (2023)

Proceedings Fifteenth International Symposium on Games, Automata, Logics, and Formal Verification
by: Achilleos, Antonis, et al.
Published: (2024)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Intuitionistic modal logic LIK4 is decidable
by: Balbiani, Philippe, et al.
Published: (2025)

Universal quantification makes automatic structures hard to decide
by: Haase, Christoph, et al.
Published: (2023)

The domino problem is decidable for robust tilesets
by: Aubrun, Nathalie, et al.
Published: (2024)

A syntactic proof of decidability for the logic of bunched implication BI
by: Ramanayake, Revantha
Published: (2016)

The Fertile Steppe: Computability Logic and the decidability of one of its fragments
by: Spadoni, Stella
Published: (2025)

Finitely accessible arboreal adjunctions and Hintikka formulae
by: Reggio, Luca, et al.
Published: (2023)

Intuitionistic modal logics: new and simpler decidability proofs for FIK and LIK
by: Balbiani, Philippe, et al.
Published: (2025)

Consistency of P-time event graphs is decidable in polynomial time (extended version)
by: Zorzenon, Davide, et al.
Published: (2023)

Boolean basis, formula size, and number of modal operators
by: Berkholz, Christoph, et al.
Published: (2024)

An abstract fixed-point theorem for Horn formula equations
by: Hetzl, Stefan, et al.
Published: (2025)

Logic for conditional strong historical necessity in branching time and analyses of an argument for future determinism
by: Ju, Fengkui
Published: (2024)

Redex -> Coq: towards a theory of decidability of Redex's reduction semantics
by: Soldevila, Mallku, et al.
Published: (2024)

Deciding branching hyperproperties for real time systems
by: Deka, Nabarun, et al.
Published: (2024)

Fairness and promptness in Muller formulas
by: Busatto-Gaston, Damien, et al.
Published: (2022)

Wider systems for linear logic with fixed points: proof theory and complexity
by: Das, Anupam, et al.
Published: (2026)

Gödel Incompleteness Theorem for PAC Learnable Theory from the view of complexity measurement
by: Ma, Zhifeng, et al.
Published: (2024)

Existential and positive games: a comonadic and axiomatic view
by: Abramsky, Samson, et al.
Published: (2025)

A simpler O(m log n) algorithm for branching bisimilarity on labelled transition systems
by: Jansen, David N., et al.
Published: (2019)

On the Axioms of Arboreal Categories
by: Jakl, Tomáš, et al.
Published: (2026)

Arboreal Categories: An Axiomatic Theory of Resources
by: Abramsky, Samson, et al.
Published: (2021)

The unstable formula theorem revisited via algorithms
by: Malliaris, Maryanthe, et al.
Published: (2022)

On the complexity of normalization for the planar $λ$-calculus
by: Das, Anupam, et al.
Published: (2024)

The complexity of Presburger arithmetic with power or powers
by: Benedikt, Michael, et al.
Published: (2023)

Hardness of monadic second-order formulae over succinct graphs
by: Gamard, Guilhem, et al.
Published: (2023)

On the complexity of Maslov's class $\overline{\text{K}}$
by: Fiuk, Oskar, et al.
Published: (2024)

A modular risk concept for complex systems
by: McGeorge, Dag, et al.
Published: (2025)