Imagen de Portada

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Kazakov, Yevgeny, Pratt-Hartmann, Ian
Formato:	Preprint
Publicado:	2009
Materias:	Logic in Computer Science Artificial Intelligence Computational Complexity F.4.1; F.2.2
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On the Complexity of the Numerically Definite Syllogistic and Related Fragments
por: Pratt-Hartmann, Ian
Publicado: (2007)

Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
por: Pratt-Hartmann, Ian
Publicado: (2008)

Logics for the Relational Syllogistic
por: Pratt-Hartmann, Ian, et al.
Publicado: (2008)

The Fluted Fragment with Transitive Relations
por: Pratt-Hartmann, Ian, et al.
Publicado: (2020)

Hypersequent Calculi Have Ackermannian Complexity
por: Balasubramanian, A. R., et al.
Publicado: (2026)

On the Satisfaction Probabilities of $k$-CNF Formulas
por: Tantau, Till
Publicado: (2022)

Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
por: Higuchi, Joaquim Reizi
Publicado: (2026)

Deducibility in the full Lambek calculus with weakening is HAck-complete
por: Greati, Vitor, et al.
Publicado: (2024)

Notes on CSPs and Polymorphisms
por: Brady, Zarathustra
Publicado: (2022)

Constant time testability of first-order logic with modulo counting on finitary graphs
por: Adler, Isolde, et al.
Publicado: (2026)

Polynomial-time Tractable Problems over the $p$-adic Numbers
por: Fehm, Arno, et al.
Publicado: (2025)

Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
por: Pratt-Hartmann, Ian
Publicado: (2004)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
por: Bodirsky, Manuel, et al.
Publicado: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
por: de Rezende, Susanna F., et al.
Publicado: (2019)

Solving Quantified Modal Logic Problems by Translation to Classical Logics
por: Steen, Alexander, et al.
Publicado: (2022)

Introducing The Maximum Common Bigraph Problem
por: Burns, Kyle, et al.
Publicado: (2026)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
por: Ito, Sohei, et al.
Publicado: (2026)

Structure-Guided Automated Reasoning
por: Bannach, Max, et al.
Publicado: (2023)

Complexity Classification Transfer for CSPs via Algebraic Products
por: Bodirsky, Manuel, et al.
Publicado: (2022)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
por: Pilipczuk, Michał, et al.
Publicado: (2025)

Formally Verifying the Safety of Pipelined Moonshot Consensus Protocol
por: Praveen, M., et al.
Publicado: (2024)

Complexity of Nonassociative Lambek Calculus with classical logic
por: Płaczek, Paweł
Publicado: (2024)

Modal Logics -- RNmatrices vs. Nmatrices
por: Coniglio, Marcelo E., et al.
Publicado: (2024)

The Hamiltonian Syllogistic
por: Pratt-Hartmann, Ian
Publicado: (2010)

Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
por: Anttila, Aleksi, et al.
Publicado: (2025)

Complexity of Łukasiewicz Modal Probabilistic Logics
por: Kozhemiachenko, Daniil, et al.
Publicado: (2025)

New Bounds for the Ideal Proof System in Positive Characteristic
por: Behera, Amik Raj, et al.
Publicado: (2025)

Expressive Power of Graph Transformers via Logic
por: Ahvonen, Veeti, et al.
Publicado: (2025)

Group Order Logic
por: Dahan, Anatole
Publicado: (2025)

T-CPDL: A Temporal Causal Probabilistic Description Logic for Developing Logic-RAG Agent
por: Yu, Hong Qing
Publicado: (2025)

Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
por: Ahvonen, Veeti, et al.
Publicado: (2024)

Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
por: Ahvonen, Veeti, et al.
Publicado: (2026)

A Fibrational Perspective on Differential Linear Logic
por: Koleilat, Jad
Publicado: (2026)

The General and Finite Satisfiability Problems for PCTL are Undecidable
por: Chodil, Miroslav, et al.
Publicado: (2024)

Experiments with Choice in Dependently-Typed Higher-Order Logic
por: Ranalter, Daniel, et al.
Publicado: (2024)

Deontic Temporal Logic for Formal Verification of AI Ethics
por: V., Priya T., et al.
Publicado: (2025)

On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic
por: Lago, Ugo Dal, et al.
Publicado: (2026)

Logic interpretations of ANN partition cells
por: Schmitt, Ingo
Publicado: (2024)

When do homomorphism counts help in query algorithms?
por: Cate, Balder ten, et al.
Publicado: (2023)

Locality, Consistency, and the Tractability Frontier
por: Simas, Tristan
Publicado: (2026)