Top 6 Arxiv Papers Today in Logic


2.013 Mikeys
#1. Degrees of Randomized Computability
Rupert Hölzl, Christopher P. Porter
In this survey we discuss work of Levin and V'yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V'yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal{A}$ and $\mathcal{B}$, $\mathcal{A}$ is less than $\mathcal{B}$ in this ordering if $\mathcal{A}\setminus\mathcal{B}$ is negligible. The degree structure associated with this ordering, the $\textit{Levin-V'yugin degrees}$ (or $\textit{LV-degrees}$), can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin-V'yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between...
more | pdf | html
Figures
None.
Tweets
mathLOb: Rupert Hölzl, Christopher P. Porter : Degrees of Randomized Computability https://t.co/hOXg9xirdu https://t.co/EnsOybgwB5
arxiv_cslo: Degrees of Randomized Computability https://t.co/m5YXkE9H29
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.009 Mikeys
#2. Constructing Wadge classes
Raphaël Carroy, Andrea Medini, Sandra Müller
We show that, assuming the Axiom of Determinacy, every non-selfdual Wadge class can be constructed by starting with those of level $\omega_1$ (that is, the ones that are closed under Borel preimages) and iteratively applying the operations of expansion and separated differences. The proof is essentially due to Louveau, and it yields at the same time a new proof of a theorem of Van Wesep (namely, that every non-selfdual Wadge class can be expressed as the result of a Hausdorff operation applied to the open sets). The exposition is self-contained, except for facts from classical descriptive set theory.
more | pdf | html
Figures
None.
Tweets
logicians: “Constructing Wadge classes”, R. Carroy, A. Medini, S. Müller. #math #logic https://t.co/TcuQ93xlrC
mathLOb: Raphaël Carroy, Andrea Medini, Sandra Müller : Constructing Wadge classes https://t.co/wwea2P8aV6 https://t.co/PodqBdAfb2
BenediktLoewe: RT @mathLOb: Raphaël Carroy, Andrea Medini, Sandra Müller : Constructing Wadge classes https://t.co/wwea2P8aV6 https://t.co/PodqBdAfb2
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.005 Mikeys
#3. Bounded homomorphisms and finitely generated fiber products of lattices
William DeMeo, Peter Mayr, Nik Ruskuc
We investigate when fiber products of lattices are finitely generated and obtain a new characterization of bounded lattice homomorphisms onto finitely presented lattices and onto lattices satisfying Whitman's condition. Specifically, for lattice epimorphisms $g\colon A\to D$, $h\colon B\to D$, where $A$, $B$ are finitely generated and $D$ is finitely presented or satisfies Whitman's condition, we show the following: If $g$ and $h$ are bounded, then their fiber product (pullback) $C=\{(a,b)\in A\times B : g(a)=h(b)\}$ is finitely generated. While the converse is not true in general, it does hold when $A$ and $B$ are free. As a consequence we obtain an exponential time algorithm to decide whether a finitely presented lattice or a finitely generated sublattice satisfying Whitman's condition is bounded. This generalizes an unpublished result of Freese and Nation.
more | pdf | html
Figures
None.
Tweets
mathLOb: William DeMeo, Peter Mayr, Nik Ruskuc : Bounded homomorphisms and finitely generated fiber products of lattices https://t.co/SE949fWjbY https://t.co/6h2DB2Br1h
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 7255
Unqiue Words: 1359

2.003 Mikeys
#4. A simplified ordinal analysis of first-order reflection
Toshiyasu Arai
In this note we give a simplified ordinal analysis of first-order reflection. An ordinal notation system $OT$ is introduced based on $\psi$-functions. Provable $\Sigma_{1}$-sentences on $L_{\omega_{1}^{CK}}$ are bounded through cut-elimination on operator controlled derivations.
more | pdf | html
Figures
None.
Tweets
mathLOb: Toshiyasu Arai : A simplified ordinal analysis of first-order reflection https://t.co/OnJat1rh5v https://t.co/9ggaSEhxSx
berenbeim: RT @mathLOb: Toshiyasu Arai : A simplified ordinal analysis of first-order reflection https://t.co/OnJat1rh5v https://t.co/9ggaSEhxSx
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

1.998 Mikeys
#5. A Canonical Model Proof of Strong Completeness for BQL
Ben Middleton
I prove using a canonical model construction that a simple extension of Visser's natural deduction system for Basic Propositional Logic is both sound and strongly complete with respect to Basic First-Order Logic (BQL). I utilize the canonical model construction to show that BQL satisfies both the Disjunction Property and the Existence Property.
more | pdf | html
Figures
None.
Tweets
mathLOb: Ben Middleton : A Canonical Model Proof of Strong Completeness for BQL https://t.co/sntny5sWT4 https://t.co/o3Rk4b9M8j
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5920
Unqiue Words: 885

1.998 Mikeys
#6. Abstract categorial grammars with island constraints and effective decidability
Sergey Slavnov
A well-known approach to treating syntactic island constraints in the setting of Lambek grammars consists in adding specific bracket modalities to the logic. We adapt this approach to abstract categorial grammars (ACG). Thus we define bracketed (implicational) linear logic, bracketed lambda-calculus, and, eventually, bracketed ACG based on bracketed $\lambda$-calculus. This allows us modeling at least simplest island constraints, typically, in the context of relativization. Next we identify specific safely bracketed ACG which, just like ordinary (bracket-free) second order ACG generate effectively decidable languages, but are sufficiently flexible to model some higher order phenomena like relativization and correctly deal with syntactic islands, at least in simple toy examples.
more | pdf | html
Figures
None.
Tweets
mathLOb: Sergey Slavnov : Abstract categorial grammars with island constraints and effective decidability https://t.co/ThpUfYbi9K https://t.co/BGt4pR8qRy
arxiv_cscl: Abstract categorial grammars with island constraints and effective decidability https://t.co/zYPXqzFPNU
arxiv_cscl: Abstract categorial grammars with island constraints and effective decidability https://t.co/zYPXqzFPNU
berenbeim: RT @mathLOb: Sergey Slavnov : Abstract categorial grammars with island constraints and effective decidability https://t.co/ThpUfYbi9K https…
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 9827
Unqiue Words: 1913

About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 160,428 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 160,428 papers.