Buchumschlag

About the Expressive Power and Complexity of Order-Invariance with Two Variables

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bednarczyk, Bartosz, Grange, Julien
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Data Complexity in Expressive Description Logics With Path Expressions
von: Bednarczyk, Bartosz
Veröffentlicht: (2024)

Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features
von: Bednarczyk, Bartosz
Veröffentlicht: (2023)

Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards (Extended Version)
von: Bednarczyk, Bartosz, et al.
Veröffentlicht: (2025)

Order-invariant cluster first-order logic on graph classes of bounded degree
von: Ghasemi, Fatemeh, et al.
Veröffentlicht: (2026)

The Adjacent Fragment and Quine's Limits of Decision
von: Bednarczyk, Bartosz, et al.
Veröffentlicht: (2024)

The Complexity and Expressive Power of Second-Order Extended Logic
von: Feng, Shiguang, et al.
Veröffentlicht: (2022)

Synthesis for prefix first-order logic on data words
von: Grange, Julien, et al.
Veröffentlicht: (2024)

A Horn extension of DL-Lite with NL data complexity
von: Arpasi, Janos, et al.
Veröffentlicht: (2026)

On Knowledge Compilation For Two-Variable First-Order Logic
von: Meng, Qiaolan, et al.
Veröffentlicht: (2026)

Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat
von: Tóth, Jan, et al.
Veröffentlicht: (2024)

Specification and Automatic Verification of Computational Reductions
von: Grange, Julien, et al.
Veröffentlicht: (2024)

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
von: Mählmann, Nikolas
Veröffentlicht: (2025)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
von: Pratt-Hartmann, Ian
Veröffentlicht: (2006)

The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable
von: Pratt-Hartmann, Ian
Veröffentlicht: (2017)

Dung's Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases
von: Mahmood, Yasir, et al.
Veröffentlicht: (2024)

Putting Perspective into OWL [sic]: Complexity-Neutral Standpoint Reasoning for Ontology Languages via Monodic S5 over Counting Two-Variable First-Order Logic (Extended Version with Appendix)
von: Álvarez, Lucía Gómez, et al.
Veröffentlicht: (2025)

Modal Logic for Reasoning About Uncertainty and Confusion
von: Bílková, Marta, et al.
Veröffentlicht: (2025)

Expressive Power of One-Shot Control Operators and Coroutines
von: Kobayashi, Kentaro, et al.
Veröffentlicht: (2025)

Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity
von: Meng, Qiaolan, et al.
Veröffentlicht: (2025)

Fusions of One-Variable First-Order Modal Logics
von: Kontchakov, Roman, et al.
Veröffentlicht: (2026)

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

The Complexity of Fragments of Second-Order HyperLTL
von: Regaud, Gaëtan, et al.
Veröffentlicht: (2025)

The Expressive Power of Transformers with Chain of Thought
von: Merrill, William, et al.
Veröffentlicht: (2023)

The Parameterized Complexity of Learning Monadic Second-Order Logic
von: van Bergerem, Steffen, et al.
Veröffentlicht: (2023)

Two-Variable Logic for Hierarchically Partitioned and Ordered Data
von: Fiuk, Oskar, et al.
Veröffentlicht: (2025)

Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
von: Pratt-Hartmann, Ian
Veröffentlicht: (2004)

Expressiveness Results for Timed Modal Mu-Calculi
von: Cleaveland, Rance, et al.
Veröffentlicht: (2023)

An Expressive Coalgebraic Modal Logic for Cellular Automata
von: Basold, Henning, et al.
Veröffentlicht: (2025)

A Two-Watched Literal Scheme for First-Order Logic
von: Briefs, Yasmine, et al.
Veröffentlicht: (2026)

On the Complexity of the Skolem Problem at Low Orders
von: Bacik, Piotr, et al.
Veröffentlicht: (2025)

Unravelling Cyclic First-Order Arithmetic
von: Leigh, Graham E., et al.
Veröffentlicht: (2025)

Towards Learning Infinite SMT Models (Work in Progress)
von: Janota, Mikoláš, et al.
Veröffentlicht: (2025)

Expressive Quantale-valued Logics for Coalgebras: an Adjunction-based Approach
von: Beohar, Harsh, et al.
Veröffentlicht: (2023)

Expressiveness of SHACL Features and Extensions for Full Equality and Disjointness Tests
von: Bogaerts, Bart, et al.
Veröffentlicht: (2022)

A Remark on the Expressivity of Asynchronous TeamLTL and HyperLTL
von: Kontinen, Juha, et al.
Veröffentlicht: (2024)

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

Towards Understanding the Expressive Power of GNNs with Global Readout
von: Funk, Maurice, et al.
Veröffentlicht: (2026)

Cyclic Implicit Complexity
von: Curzi, Gianluca, et al.
Veröffentlicht: (2021)

Unification with Simple Variable Restrictions and Admissibility of $Π_{2}$-rules
von: Almeida, Rodrigo Nicolau, et al.
Veröffentlicht: (2024)

About enveloping algebras of direct sums
von: Duchamp, Gérard Henry Edmond, et al.
Veröffentlicht: (2024)