### Top 10 Arxiv Papers Today in Formal Languages And Automata Theory

##### #1. On random primitive sets, directable NDFAs and the generation of slowly synchronizing DFAs
###### Costanza Catalano, Raphaël M. Jungers
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
###### Tweets
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 15622
Unqiue Words: 2703

##### #2. A Faster-Than Relation for Semi-Markov Decision Processes
###### Mathias R. Pedersen, Giorgio Bacci, Kim G. Larsen
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.
###### Tweets
ComputerPapers: A Faster-Than Relation for Semi-Markov Decision Processes. https://t.co/YtuiqDO3X3
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11079
Unqiue Words: 2250

##### #3. The problem with probabilistic DAG automata for semantic graphs
###### Ieva Vasiljeva, Sorcha Gilroy, Adam Lopez
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.
###### Tweets
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.
###### Other stats
Sample Sizes : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Authors: 3
Total Words: 6659
Unqiue Words: 1738

##### #4. 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

##### #5. Visibly Pushdown Languages and Free Profinite Algebras
###### Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange
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.
###### Tweets
ComputerPapers: Visibly Pushdown Languages and Free Profinite Algebras. https://t.co/0XZDa7SQSh
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 14014
Unqiue Words: 2489

##### #6. Bounded Synthesis of Register Transducers
###### Ayrat Khalimov, Benedikt Maderbacher, Roderick Bloem
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.
###### Tweets
ComputerPapers: Bounded Synthesis of Register Transducers. https://t.co/ZpM78V7wBu
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10116
Unqiue Words: 2179

##### #7. Transfinite Lyndon words
###### Olivier Carton, Luc Boasson
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.
###### Tweets
ComputerPapers: Transfinite Lyndon words. https://t.co/z7cuRsxWqf
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 24929
Unqiue Words: 2328

##### #8. 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

##### #9. 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

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

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 72,893 papers.