All Questions
Tagged with automata-theory nt.number-theory
3 questions
4
votes
2
answers
227
views
Given an automatic set $S$ coming from a DFA $M$ when read little-endian, is $\overline{d}(S)$ at most the Büchi acceptance probability of $M$?
Note: I've entirely rewritten this question! Originally it was just the third formulation, take note of that when reading answers.
Let's say $S$ is a $b$-automatic set, and let's say $M$ is a DFA ...
- 2,585
3
votes
1
answer
1k
views
Collatz conjecture— finite state machine transducer construction, origination?
wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...
- 529
1
vote
0
answers
64
views
Does Frobenius number increase if bound on input increases?
The Frobenius number F is the largest number not expressible as a non-negative linear combination of some set of positive integers $\{a_i\}$, where, $a_i$ has gcd 1. Denote $maxF(n)$ as the maximum of ...
