We tackle the problem of the randomized generation of slowly synchronizing
deterministic automata (DFAs) by generating random primitive sets of matrices.
We show that when the randomized procedure is too simple the exponent of the
generated sets is O(n log n) with high probability, thus the procedure fails to
return DFAs with large reset threshold. We extend this result to random
nondeterministic automata (NDFAs) by showing, in particular, that a uniformly
sampled NDFA has both a 2-directing word and a 3-directing word of length O(n
log n) with high probability. We then present a more involved randomized
algorithm that manages to generate DFAs with large reset threshold and we
finally leverage this finding for exhibiting new families of DFAs with reset
threshold of order $ \Omega(n^2/4) $.

more |
pdf
| html
MathPaper:
On random primitive sets, directable NDFAs and the generation of slowly synchronizing DFAs. https://t.co/nkuseGK8A7

MUKULBHALLA7:
https://t.co/csZzdjGs4Y

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 15622

Unqiue Words: 2703

When modeling concurrent or cyber-physical systems, non-functional
requirements such as time are important to consider. In order to improve the
timing aspects of a model, it is necessary to have some notion of what it means
for a process to be faster than another, which can guide the stepwise
refinement of the model. To this end we study a faster-than relation for
semi-Markov decision processes and compare it to standard notions for relating
systems. We show that checking whether a system is faster than another one is
undecidable, but as a positive result we give a decision procedure for
approximating it. Furthermore, we consider the compositional aspects of this
relation, and show that the faster-than relation is not a precongruence with
respect to parallel composition, hence giving rise to so-called parallel timing
anomalies. We take the first steps toward understanding this problem by
identifying decidable conditions sufficient to avoid parallel timing anomalies
in the absence of non-determinism.

more |
pdf
| html
None.

ComputerPapers:
A Faster-Than Relation for Semi-Markov Decision Processes. https://t.co/YtuiqDO3X3

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 11079

Unqiue Words: 2250

Semantic representations in the form of directed acyclic graphs (DAGs) have
been introduced in recent years, and to model them, we need probabilistic
models of DAGs. One model that has attracted some attention is the DAG
automaton, but it has not been studied as a probabilistic model. We show that
some DAG automata cannot be made into useful probabilistic models by the nearly
universal strategy of assigning weights to transitions. The problem affects
single-rooted, multi-rooted, and unbounded-degree variants of DAG automata, and
appears to be pervasive. It does not affect planar variants, but these are
problematic for other reasons.

more |
pdf
| html
None.

there_are_two_:
In time for tonight’s Great @BritishBakeOff final, here is a mathematical / computational linguistics research paper with #GBBO-themed examples, by Ieva Vasiljeva and @SorchaGilroy.
https://t.co/ngWI1EP3aq https://t.co/FiRmSpZFd1

there_are_two_:
In this paper, Ieva Vasiljeva and @SorchaGilroy give you a simple and elegant proof that it is *impossible* to define a probabilistic model by weighting the transitions of a DAG automaton.
https://t.co/ngWI1EP3aq https://t.co/DFI2oaQWGl

there_are_two_:
In time for tonight’s Great @BritishBakeOff final, here is a mathematical / computational linguistics research paper with #GBBO-themed examples, by Ieva Vasiljeva and @SorchaGilroy.
https://t.co/ngWI1EP3aq https://t.co/Ci4AtqaMuQ

arxiv_cscl:
The problem with probabilistic DAG automata for semantic graphs https://t.co/zwFtuieTsl

arxiv_cscl:
The problem with probabilistic DAG automata for semantic graphs https://t.co/zwFtuieTsl

None.

None.

Sample Sizes : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Authors: 3

Total Words: 6659

Unqiue Words: 1738

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

We build a notion of algebraic recognition for visibly pushdown languages by
finite algebraic objects. These come with a typical Eilenberg relationship, now
between classes of visibly pushdown languages and classes of finite algebras.
Building on that algebraic foundation, we further construct a topological
object with one purpose being the possibility to derive a notion of equations,
through which it is possible to prove that some given visibly pushdown language
is not part of a certain class (or to even show decidability of the
membership-problem of the class in some cases). In particular, we obtain a
special instance of Reiterman's theorem for pseudo-varieties. These findings
are then employed on two subclasses of the visibly pushdown languages, for
which we derive concrete sets of equations. For some showcase languages, these
equations are utilised to prove non-membership to the previously described
classes.

more |
pdf
| html
None.

ComputerPapers:
Visibly Pushdown Languages and Free Profinite Algebras. https://t.co/0XZDa7SQSh

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 14014

Unqiue Words: 2489

Reactive synthesis aims at automatic construction of systems from their
behavioural specifications. The research mostly focuses on synthesis of systems
dealing with Boolean signals. But real-life systems are often described using
bit-vectors, integers, etc. Bit-blasting would make such systems unreadable,
hit synthesis scalability, and is not possible for infinite data-domains. One
step closer to real-life systems are register transducers: they can store
data-input into registers and later output the content of a register, but they
do not directly depend on the data-input, only on its comparison with the
registers. Previously it was proven that synthesis of register transducers from
register automata is undecidable, but there the authors considered transducers
equipped with the unbounded queue of registers. First, we prove the problem
becomes decidable if bound the number of registers in transducers, by reducing
the problem to standard synthesis of Boolean systems. Second, we show how to
use quantified temporal logic, instead of...

more |
pdf
| html
None.

ComputerPapers:
Bounded Synthesis of Register Transducers. https://t.co/ZpM78V7wBu

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 10116

Unqiue Words: 2179

In this paper, we extend the notion of Lyndon word to transfinite words. We
prove two main results. We first show that, given a transfinite word, there
exists a unique factorization in Lyndon words that are locally decreasing, a
relaxation of the condition used in the case of finite words. In the part, we
prove that the factorization of a rational word has a special form and that it
can be computed in polynomial time from a rational expression describing the
word.

more |
pdf
| html
None.

ComputerPapers:
Transfinite Lyndon words. https://t.co/z7cuRsxWqf

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 24929

Unqiue Words: 2328

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

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 72,893 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible