Buchumschlag

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bruse, Florian, Lange, Martin
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Logic in Computer Science 68Q19 (Primary), 68Q15 (Secondary), 03B70 (Secondary), 03B45 (Secondary) F.2.0; F.4.1; F.4.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
von: Lopez, Aliaume
Veröffentlicht: (2024)

Disproving Termination of Non-Erasing Sole Combinatory Calculus with Tree Automata (Full Version)
von: Nakano, Keisuke, et al.
Veröffentlicht: (2024)

Languages of Words of Low Automatic Complexity Are Hard to Compute
von: Chen, Joey, et al.
Veröffentlicht: (2025)

A correspondence between the time and space complexity
von: Latkin, Ivan V.
Veröffentlicht: (2023)

Encoding Argumentation Frameworks to Propositional Logic Systems
von: Tang, Shuai, et al.
Veröffentlicht: (2025)

Recursive windows for grammar logics of bounded density
von: Gasquet, Olivier
Veröffentlicht: (2025)

PSPACE-completeness of bimodal transitive weak-density logic
von: Balbiani, Philippe, et al.
Veröffentlicht: (2025)

$\mathbb{N}$-polyregular functions arise from well-quasi-orderings
von: Lopez, Aliaume
Veröffentlicht: (2024)

Relational Connectors and Heterogeneous Bisimulations
von: Nora, Pedro, et al.
Veröffentlicht: (2024)

Determination of the fifth Busy Beaver value
von: The bbchallenge Collaboration, et al.
Veröffentlicht: (2025)

Algebraic Proof Theory for Infinitary Action Logic
von: Fussner, Wesley, et al.
Veröffentlicht: (2025)

The Solver's Paradox in Formal Problem Spaces
von: Rosko, Milan
Veröffentlicht: (2025)

A Logic For Fresh Labelled Transition Systems
von: Bandukara, Mohamed H, et al.
Veröffentlicht: (2025)

Computing Distinguishing Formulae for Threshold-Based Behavioural Distances
von: Forster, Jonas, et al.
Veröffentlicht: (2026)

Proof complexity of universal algebra in a CSP dichotomy proof
von: Gaysin, Azza
Veröffentlicht: (2024)

An Expressive Trace Logic for Recursive Programs
von: Gurov, Dilian, et al.
Veröffentlicht: (2024)

Univalent Material Set Theory
von: Gylterud, Håkon Robbestad, et al.
Veröffentlicht: (2023)

Higher-Order Pattern Unification Modulo Similarity Relations
von: Dundua, Besik, et al.
Veröffentlicht: (2025)

Terminal Coalgebras and Non-wellfounded Sets in Homotopy Type Theory
von: Gylterud, Håkon Robbestad, et al.
Veröffentlicht: (2020)

Logics of polyhedral reachability
von: Bezhanishvili, Nick, et al.
Veröffentlicht: (2024)

Behavioural Conformances based on Lax Couplings
von: Wild, Paul, et al.
Veröffentlicht: (2025)

Agent Interpolation for Knowledge
von: Bílková, Marta, et al.
Veröffentlicht: (2025)

Simply-typed constant-domain modal lambda calculus I: distanced beta reduction and combinatory logic
von: Walsh, Sean
Veröffentlicht: (2024)

Quantitative Graded Semantics and Spectra of Behavioural Metrics
von: Forster, Jonas, et al.
Veröffentlicht: (2023)

2-Coherent Internal Models of Homotopical Type Theory
von: Chen, Joshua
Veröffentlicht: (2025)

A declarative approach to specifying distributed algorithms using three-valued modal logic
von: Gabbay, Murdoch J., et al.
Veröffentlicht: (2025)

Run supports and initial algebra supports of weighted automata
von: Droste, Manfred, et al.
Veröffentlicht: (2024)

Graded Semantics and Graded Logics for Eilenberg-Moore Coalgebras
von: Forster, Jonas, et al.
Veröffentlicht: (2023)

Generalized Kantorovich-Rubinstein Duality beyond Hausdorff and Kantorovich
von: Wild, Paul, et al.
Veröffentlicht: (2025)

Provability in BI's Sequent Calculus is Decidable
von: Gheorghiu, Alexander, et al.
Veröffentlicht: (2021)

Computability of Initial Value Problems
von: Brattka, Vasco, et al.
Veröffentlicht: (2024)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
von: Dorochko, Leonid, et al.
Veröffentlicht: (2026)

Relative Constructibility via Generalised Sequential Algorithms
von: Lau, Desmond
Veröffentlicht: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
von: Huseynzade, Rafig
Veröffentlicht: (2025)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)

Gödel Mirror: A Formal System For Contradiction-Driven Recursion
von: Chan, Jhet
Veröffentlicht: (2025)

A Modular Lean 4 Framework for Confluence and Strong Normalization of Lambda Calculi with Products and Sums
von: Ramos, Arthur, et al.
Veröffentlicht: (2025)

Decision Problems on Copying and Shuffling
von: Halava, Vesa, et al.
Veröffentlicht: (2023)

Complete Game Logic with Sabotage
von: Wafa, Noah Abou El, et al.
Veröffentlicht: (2024)

Complete Robust Hybrid Systems Reachability
von: Wafa, Noah Abou El, et al.
Veröffentlicht: (2026)