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
None.

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

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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
None.

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

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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
None.

mathLOb:
William DeMeo, Peter Mayr, Nik Ruskuc : Bounded homomorphisms and finitely generated fiber products of lattices https://t.co/SE949fWjbY https://t.co/6h2DB2Br1h

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 7255

Unqiue Words: 1359

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
None.

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

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

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
None.

mathLOb:
Ben Middleton : A Canonical Model Proof of Strong Completeness for BQL https://t.co/sntny5sWT4 https://t.co/o3Rk4b9M8j

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 5920

Unqiue Words: 885

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
None.

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…

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 9827

Unqiue Words: 1913

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible