Imagen de Portada

The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Pratt-Hartmann, Ian
Formato:	Preprint
Publicado:	2017
Materias:	Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
por: Kazakov, Yevgeny, et al.
Publicado: (2009)

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

Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
por: Kieronski, Emanuel, et al.
Publicado: (2016)

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

On the Satisfiability of Local First-Order Logics with Data
por: Bollig, Benedikt, et al.
Publicado: (2023)

Checking Satisfiability of Hyperproperties using First-Order Logic
por: Beutner, Raven, et al.
Publicado: (2025)

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

Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions
por: Artale, Alessandro, et al.
Publicado: (2025)

A Decidable Bundled Fragment of First-Order Modal Logic Without Finite Model Property
por: Joshi, Varad, et al.
Publicado: (2025)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
por: Barloy, Corentin, et al.
Publicado: (2025)

Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic
por: Kurucz, Agi, et al.
Publicado: (2023)

On Knowledge Compilation For Two-Variable First-Order Logic
por: Meng, Qiaolan, et al.
Publicado: (2026)

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

Interpolant Existence is Undecidable for Two-Variable First-Order Logic with Two Equivalence Relations
por: Wolter, Frank, et al.
Publicado: (2024)

Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property
por: Elad, Neta, et al.
Publicado: (2026)

Decidability of Querying First-Order Theories via Countermodels of Finite Width
por: Feller, Thomas, et al.
Publicado: (2023)

Decidability of Quantum Modal Logic
por: Tokuo, Kenji
Publicado: (2026)

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

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

The Syllogistic with Unity
por: Pratt-Hartmann, Ian
Publicado: (2011)

Dynamic Probability Logic: Decidability & Computability
por: Chopoghloo, Somayeh, et al.
Publicado: (2024)

Decidability of Quasi-Dense Modal Logics
por: Ostropolski-Nalewaja, Piotr, et al.
Publicado: (2024)

Craig Interpolation for Decidable First-Order Fragments
por: Cate, Balder ten, et al.
Publicado: (2023)

Fusions of One-Variable First-Order Modal Logics
por: Kontchakov, Roman, et al.
Publicado: (2026)

Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
por: Lutz, Carsten, et al.
Publicado: (2024)

Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite Validity
por: Nakamura, Yoshiki
Publicado: (2023)

The Satisfiability and Validity Problems for Probabilistic Computational Tree Logic are Highly Undecidable
por: Chodil, Miroslav, et al.
Publicado: (2025)

Taking Bi-Intuitionistic Logic First-Order: A Proof-Theoretic Investigation via Polytree Sequents
por: Lyon, Tim S., et al.
Publicado: (2024)

Set Automata and Limits of Decidability of Two-Variable Logic on Data Words
por: Guha, Shibashis, et al.
Publicado: (2026)

A Two-Watched Literal Scheme for First-Order Logic
por: Briefs, Yasmine, et al.
Publicado: (2026)

On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories
por: Haase, Christoph, et al.
Publicado: (2024)

Decidability of Two Truly Concurrent Equivalences for Finite Bounded Petri Nets
por: Cesco, Arnaldo, et al.
Publicado: (2021)

The Adjacent Fragment and Quine's Limits of Decision
por: Bednarczyk, Bartosz, et al.
Publicado: (2024)

Distributed First Order Logic
por: Ghidini, Chiara, et al.
Publicado: (2015)

Interpolation in First-Order Logic
por: Cate, Balder ten, et al.
Publicado: (2025)

Functions Definable by Numerical Set-Expressions
por: Pratt-Hartmann, Ian, et al.
Publicado: (2009)

Complex Algebras of Arithmetic
por: Düntsch, Ivo, et al.
Publicado: (2009)

Deciding Separation Logic with Pointer Arithmetic and Inductive Definitions
por: Su, Wanyun, et al.
Publicado: (2024)

Possibilistic Computation Tree Logic: Decidability and Complete Axiomatization
por: Li, Yongming
Publicado: (2025)

Deciding Predicate Logical Theories of Real-Valued Functions
por: Ratschan, Stefan
Publicado: (2023)