Imagen de Portada

Universal quantification makes automatic structures hard to decide

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Haase, Christoph, Piórkowski, Radoslaw
Formato:	Preprint
Publicado:	2023
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

Scoped MSO, Register Automata, and Expressions: Equivalence over Data Words
por: Piórkowski, Radosław
Publicado: (2026)

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

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

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

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

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

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

The complexity of deciding characteristic formulae in van Glabbeek's branching-time spectrum
por: Aceto, Luca, et al.
Publicado: (2024)

Finding hardness reductions automatically using SAT solvers
por: Bergold, Helena, et al.
Publicado: (2024)

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

An efficient quantifier elimination procedure for Presburger arithmetic
por: Haase, Christoph, et al.
Publicado: (2024)

Realizing the totally unordered structure of ordinals
por: Fontanella, Laura, et al.
Publicado: (2025)

Universal Horn Sentences and the Joint Embedding Property
por: Bodirsky, Manuel, et al.
Publicado: (2021)

Universal Proof Theory, TACL 2022 Lecture Notes
por: Iemhoff, Rosalie, et al.
Publicado: (2023)

OSVAuto: automatic proofs about functional specifications in OS verification
por: Wu, Yulun, et al.
Publicado: (2024)

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

Universal Proof Theory: Semi-analytic Rules and Uniform Interpolation
por: Tabatabai, Amirhossein Akbar, et al.
Publicado: (2018)

Universal Proof Theory: Semi-analytic Rules and Craig Interpolation
por: Tabatabai, Amirhossein Akbar, et al.
Publicado: (2018)

On the logical structure of some maximality and well-foundedness principles equivalent to choice principles
por: Herbelin, Hugo
Publicado: (2024)

Correct Black-Box Monitors for Distributed Deadlock Detection: Formalisation and Implementation (Technical Report)
por: Rowicki, Radosław Jan, et al.
Publicado: (2025)

Interpretation of Inaccessible Sets in Martin-Löf Type Theory with One Mahlo Universe
por: Takahashi, Yuta
Publicado: (2024)

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

The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
por: Brunar, Johanna, et al.
Publicado: (2025)

Abstract computation over first-order structures. Part IIa: Moschovakis' operator and other non-determinisms
por: Gaßner, Christine
Publicado: (2025)

Abstract computation over first-order structures. Part IIb: Moschovakis' operator and other non-determinisms
por: Gaßner, Christine
Publicado: (2025)

Abstract computation over first-order structures. Part I: Deterministic and non-deterministic BSS RAMs
por: Gaßner, Christine
Publicado: (2025)

The addition of temporal neighborhood makes the logic of prefixes and sub-intervals EXPSPACE-complete
por: Bozzelli, L., et al.
Publicado: (2022)

Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
por: Pinsker, Michael, et al.
Publicado: (2025)

Topologically valued transition structures
por: Collinson, Matthew
Publicado: (2026)

Positivity-hardness results on Markov decision processes
por: Piribauer, Jakob, et al.
Publicado: (2023)

Stabilized profunctors and stable species of structures
por: Fiore, Marcelo, et al.
Publicado: (2023)

Local structure of idempotent algebras I
por: Bulatov, Andrei A.
Publicado: (2020)

Machine Space I: Weak exponentials and quantification over compact spaces
por: Faul, Peter F., et al.
Publicado: (2022)

The equivariant model structure on cartesian cubical sets
por: Awodey, Steve, et al.
Publicado: (2024)

(Pointed) Univalence in Universe Category Models of Type Theory
por: Kapulkin, Chris, et al.
Publicado: (2025)

Unknown Biases and Timing Constraints in Timed Automata
por: Haase, Darion, et al.
Publicado: (2024)

Generating Theorems by Generating Proof Structures
por: Wernhard, Christoph
Publicado: (2026)

Craig-Lyndon Interpolation for the Logic of Here and There with a Variation of Mints' Sequent System
por: Wernhard, Christoph
Publicado: (2026)

Interpolation with Automated First-Order Reasoning
por: Wernhard, Christoph
Publicado: (2025)

RustSAT: A Library For SAT Solving in Rust
por: Jabs, Christoph
Publicado: (2025)