We use a semigroup-theoretic construction by Peter Higgins in order to
produce, for each even $n$, an $n$-state and 3-letter synchronizing automaton
with the following two features: 1) all its input letters act as idempotent
selfmaps of rank at most $\dfrac{n}2$; 2) its reset threshold is asymptotically
equal to $\dfrac{n^2}2$.

more |
pdf
| html
None.

ComputerPapers:
Slowly Synchronizing Automata with Idempotent Letters of Low Rank. https://t.co/WTmqZcewii

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 5073

Unqiue Words: 1303

Pushdown systems (PDSs) are a natural model for sequential programs, but they
can fail to accurately represent the way an assembly stack actually operates.
Indeed, one may want to access the part of the memory that is below the current
stack or base pointer, hence the need for a model that keeps track of this part
of the memory.
To this end, we introduce pushdown systems with an upper stack (UPDSs), an
extension of PDSs where symbols popped from the stack are not destroyed but
instead remain just above its top, and may be overwritten by later push rules.
We prove that the sets of successors post* and predecessors pre* of a regular
set of configurations of such a system are not always regular, but that post*
is context-sensitive, so that we can decide whether a single configuration is
forward reachable or not.
In order to under-approximate pre* in a regular fashion, we consider a
bounded-phase analysis of UPDSs, where a phase is a part of a run during which
either push or pop rules are forbidden. We then present a method...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 9509

Unqiue Words: 1803

We study a class of algebras that can be used as recognisers for regular
languages of infinite trees.

more |
pdf
| html
None.

ComputerPapers:
Branch-Continuous Tree Algebras. https://t.co/EJUk8hnxyr

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 23711

Unqiue Words: 3019

Motivated by real-time monitoring and data processing applications, we
develop a formal theory of quantitative queries for streaming data that can be
evaluated efficiently. We consider the model of unambiguous Cost Register
Automata (CRAs), which are machines that combine finite-state control (for
identifying regular patterns) with a finite set of data registers (for
computing numerical aggregates). The definition of CRAs is parameterized by the
collection of numerical operations that can be applied to the registers. These
machines give rise to the class of streamable regular transductions (SR), and
to the class of streamable linear regular transductions (SLR) when the register
updates are copyless, i.e. every register appears at most once the
right-hand-side expressions of the updates. We give a logical characterization
of the class SR (resp., SLR) using MSO-definable transformations from strings
to DAGs (resp., trees) without backward edges. Additionally, we establish that
the two classes SR and SLR are closed under operations...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 19437

Unqiue Words: 3378

In this paper we consider the notion of normality of sequences in shifts of
finite type. A sequence is normal if the frequency of each block exists and is
equal to the Parry measure of the block. We give a characterization of
normality in terms of incompressibility by lossless transducers. The result was
already known in the case of the full shift.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 6346

Unqiue Words: 1442

We consider equivalence and containment problems for word transductions.
These problems are known to be undecidable when the transductions are relations
between words realized by non-deterministic transducers, and become decidable
when restricting to functions from words to words. Here we prove that
decidability can be equally recovered by adopting a slightly different, but
natural semantics, called origin semantics and introduced by Bojanczyk in 2014.
Specifically, we prove that the equivalence and containment problems for
two-way word transducers in the origin semantics are PSPACE-complete. We also
consider a variant of the containment problem where two-way transducers are
compared under the origin semantics, but in a more relaxed way, by allowing
distortions of the origins. The possible distortions are described by means of
a resynchronization relation. We propose a logical formalism for describing a
broad class of resynchronizations, while preserving the decidability of the
variant of the containment problem.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 14127

Unqiue Words: 2383

Differential privacy is a widely studied notion of privacy for various models
of computation. Technically, it is based on measuring differences between
probability distributions. We study $\epsilon,\delta$-differential privacy in
the setting of labelled Markov chains. While the exact differences relevant to
$\epsilon,\delta$-differential privacy are not computable in this framework, we
propose a computable bisimilarity distance that yields a sound technique for
measuring $\delta$, the parameter that quantifies deviation from pure
differential privacy. We show this bisimilarity distance is always rational,
the associated threshold problem is in NP, and the distance can be computed
exactly with polynomially many calls to an NP oracle.

more |
pdf
| html
None.

ComputerPapers:
Bisimilarity Distances for Approximate Differential Privacy. https://t.co/eJTcCpzj0S

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 11087

Unqiue Words: 2596

Several distinct techniques have been proposed to design quasi-polynomial
algorithms for solving parity games since the breakthrough result of Calude,
Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures
and register games. We argue that all those techniques can be viewed as
instances of the separation approach to solving parity games, a key technical
component of which is constructing (explicitly or implicitly) an automaton that
separates languages of words encoding plays that are (decisively) won by either
of the two players. Our main technical result is a quasi-polynomial lower bound
on the size of such separating automata that nearly matches the current best
upper bounds. This forms a barrier that all existing approaches must overcome
in the ongoing quest for a polynomial-time algorithm for solving parity games.
The key and fundamental concept that we introduce and study is a universal
ordered tree. The technical highlights are a quasi-polynomial lower bound on
the size of universal ordered trees and a...

more |
pdf
| html
None.

DO:
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. https://t.co/z1W6cy4Vsw

None.

None.

Sample Sizes : None.

Authors: 6

Total Words: 14294

Unqiue Words: 2488

We prove various results about the largest exponent of a repetition in a
factor of the Thue-Morse word, when that factor is considered as a circular
word. Our results confirm and generalize previous results of Fitzpatrick and
Aberkane & Currie.

more |
pdf
| html
None.

MathPaper:
Circular critical exponents for Thue-Morse factors. https://t.co/5d3yypLIK5

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 5589

Unqiue Words: 1647

A cryptarithm is a mathematical puzzle where given an arithmetic equation
written with letters rather than numerals, a player must discover an assignment
of numerals on letters that makes the equation hold true. In this paper, we
propose a method to construct a DFA that accepts cryptarithms that admit
(unique) solutions for each base. We implemented the method and constructed a
DFA for bases $k \le 7$. Those DFAs can be used as complete catalogues of
cryptarithms,whose applications include enumeration of and counting the exact
numbers $G_k(n)$ of cryptarithm instances with $n$ digits that admit base-$k$
solutions. Moreover, explicit formulas for $G_2(n)$ and $G_3(n)$ are given.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 5564

Unqiue Words: 1531

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 57,756 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible