Top 10 Arxiv Papers Today in Formal Languages And Automata Theory

#1. Slowly Synchronizing Automata with Idempotent Letters of Low Rank
Mikhail Volkov
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.
Tweets
ComputerPapers: Slowly Synchronizing Automata with Idempotent Letters of Low Rank. https://t.co/WTmqZcewii
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5073
Unqiue Words: 1303

#2. Reachability Analysis of Pushdown Systems with an Upper Stack
Adrien Pommellet, Marcio Diaz, Tayssir Touili
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.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9509
Unqiue Words: 1803

#3. Branch-Continuous Tree Algebras
Achim Blumensath
We study a class of algebras that can be used as recognisers for regular languages of infinite trees.
more | pdf | html
None.
Tweets
ComputerPapers: Branch-Continuous Tree Algebras. https://t.co/EJUk8hnxyr
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 23711
Unqiue Words: 3019

#4. Streamable Regular Transductions
Rajeev Alur, Dana Fisman, Konstantinos Mamouras, Mukund Raghothaman, Caleb Stanford
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.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 19437
Unqiue Words: 3378

#5. On normality in shifts of finite type
Nicolás Álvarez, Olivier Carton
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.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6346
Unqiue Words: 1442

#6. Origin-equivalence of two-way word transducers is in PSPACE
Sougata Bose, Anca Muscholl, Vincent Penelle, Gabriele Puppis
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.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 14127
Unqiue Words: 2383

#7. Bisimilarity Distances for Approximate Differential Privacy
Dmitry Chistikov, Andrzej S. Murawski, David Purser
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.
Tweets
ComputerPapers: Bisimilarity Distances for Approximate Differential Privacy. https://t.co/eJTcCpzj0S
None.
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11087
Unqiue Words: 2596

#8. Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, Paweł Parys
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.
Tweets
DO: Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. https://t.co/z1W6cy4Vsw
None.
None.
Other stats
Sample Sizes : None.
Authors: 6
Total Words: 14294
Unqiue Words: 2488

#9. Circular critical exponents for Thue-Morse factors
Jeffrey Shallit, Ramin Zarifi
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.
Tweets
MathPaper: Circular critical exponents for Thue-Morse factors. https://t.co/5d3yypLIK5
None.
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 5589
Unqiue Words: 1647

#10. Enumerating Cryptarithms Using Deterministic Finite Automata
Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka, Takashi Horiyama, Ayumi Shinohara
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.
Other stats
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.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
Stats
Tracking 57,756 papers.