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.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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.

Sample Sizes : None.

Authors: 3

Total Words: 9630

Unqiue Words: 1953

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.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible