Cover Image

Description Complexity of Unary Structures in First-Order Logic with Links to Entropy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jaakkola, Reijo, Kuusisto, Antti, Vilander, Miikka
Format:	Preprint
Published:	2024
Subjects:	Logic Logic in Computer Science 03C13 (Primary) 68R01, 94A17, 68Q30 (Secondary) F.4.1; G.2.0; E.4
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Why this and not that? A Logic-based Framework for Contrastive Explanations
by: Geibinger, Tobias, et al.
Published: (2025)

Recursive windows for grammar logics of bounded density
by: Gasquet, Olivier
Published: (2025)

PSPACE-completeness of bimodal transitive weak-density logic
by: Balbiani, Philippe, et al.
Published: (2025)

The equational theory of the Weihrauch lattice with (iterated) composition
by: Pradic, Cécilia
Published: (2024)

Arithmetics within the Linear Time Hierarchy
by: Pollett, Chris
Published: (2025)

Encoding Argumentation Frameworks to Propositional Logic Systems
by: Tang, Shuai, et al.
Published: (2025)

Higher-Order Pattern Unification Modulo Similarity Relations
by: Dundua, Besik, et al.
Published: (2025)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
by: Bruse, Florian, et al.
Published: (2026)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)

Globally Interpretable Classifiers via Boolean Formulas with Dynamic Propositions
by: Jaakkola, Reijo, et al.
Published: (2024)

Proof complexity of universal algebra in a CSP dichotomy proof
by: Gaysin, Azza
Published: (2024)

On the relative asymptotic expressivity of inference frameworks
by: Koponen, Vera, et al.
Published: (2022)

Hyperfiniteness on Topological Ramsey Spaces
by: Bursics, Balázs, et al.
Published: (2024)

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

Logic in Mathematics and Computer Science
by: Zach, Richard
Published: (2024)

Computability of Initial Value Problems
by: Brattka, Vasco, et al.
Published: (2024)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Interpretable classifiers for tabular data via discretization and feature selection
by: Jaakkola, Reijo, et al.
Published: (2024)

Behavioural Conformances based on Lax Couplings
by: Wild, Paul, et al.
Published: (2025)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

Monoid Theory in Alonzo: A Little Theories Formalization in Simple Type Theory
by: Farmer, William M., et al.
Published: (2023)

A classification of bisimilarities for general Markov decision processes
by: Moroni, Martín Santiago, et al.
Published: (2024)

The complexity of bisimilarity on pointmass processes
by: Moroni, Martín Santiago, et al.
Published: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Topological Logics with Connectedness over Euclidean Spaces
by: Kontchakov, Roman, et al.
Published: (2011)

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

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

The Orientation Boundary for Step-Duplicating Recursors: Mechanized Impossibility, Escape, and Certification
by: Rahnama, Moses
Published: (2025)

Quantitative Graded Semantics and Spectra of Behavioural Metrics
by: Forster, Jonas, et al.
Published: (2023)

Languages of Words of Low Automatic Complexity Are Hard to Compute
by: Chen, Joey, et al.
Published: (2025)

Refutability as Recursive as Provability
by: Cattabriga, Paola
Published: (2024)

On the Walsh and Fourier-Hadamard Supports of Boolean Functions From a Quantum Viewpoint
by: Carlet, Claude, et al.
Published: (2022)

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

Graded Monad Coalgebras for Continuous-Time Transition Systems
by: Di Lavore, Elena, et al.
Published: (2026)

Determination of the fifth Busy Beaver value
by: The bbchallenge Collaboration, et al.
Published: (2025)

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
by: Lopez, Aliaume
Published: (2024)