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

##### #1. Algebraic and Combinatorial Tools for State Complexity : Application to the Star-Xor Problem
###### Pascal Caron, Edwin Hamel-de le Court, Jean-Gabriel Luque
We investigate the state complexity of the star of symmetrical differences using modifiers and monsters. A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton. These recent theoretical concepts allow one to find easily the desired state complexity. We then exhibit a witness with a constant size alphabet.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #2. State Complexity of the Multiples of the Thue-Morse Set
###### Émilie Charlier, Célia Cisternino, Adeline Massuir
The Thue-Morse set T is the set of those non-negative integers whose binary expansions have an even number of 1. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word abbabaabbaababba..., which is the fixed point starting with a of the word morphism sending a to ab and b to ba. The numbers in T are sometimes called the evil numbers. We obtain an exact formula for the state complexity (i.e. the number of states of its minimal automaton) of the multiplication by a constant of the Thue-Morse set with respect to any integer base b which is a power of 2. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all 2^p-expansions of the set mT for any positive integers m and p. The used method is general for any b-recognizable set of integers. As an application, we obtain a decision procedure running in quadratic time for the problem of deciding whether a given 2^p-recognizable set is equal to some multiple of the Thue-Morse set.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9630
Unqiue Words: 1953

##### #3. On the Order Type of Scattered Context-Free Orderings
###### Kitti Gelle, Szabolcs Iván
We show that if a context-free grammar generates a language whose lexicographic ordering is well-ordered of type less than $\omega^2$, then its order type is effectively computable.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

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 192,914 papers.

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