New answers tagged automata-theory
3
I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states.
An exponential lower bound on $f$ can be given as follows.
Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that ...
0
As Emil explained in a comment:
The sides are interchangable when defining the Rabin condition - my professor defined the left side as the one that is required to be visited infinitely often while Wikipedia and the paper I've mentioned define the right side as the one that is required to be visited infinitely often.
Whichever the side that has to be visited ...
2
I seems that I was quite confused back then. This language class is precisely the language class of those languages, whose commutative closure is regular.
Let $\Sigma = \{a_1, \ldots, a_k\}$. One implication is given in the question. For the other, suppose the commutative closure of $L \subseteq \Sigma^*$ is regular, i.e., the set $p^{-1}(p(L))$ is regular.
...
1
After more and more digging, here is what I found:
First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition.
Specifically, theorem 4.26 indicates that the provided algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A.
This was my original understanding, so the answer ...
4
What if you don't assume a finite state space, but rather allow the set Q to be R,
yet require delta to be "nice", e.g., smooth and easily computable?
Then this presumably defines a restricted class of functions over sequences of reals. Has this question been studied?
10
Automata over infinite alphabets have been studied in many contexts (see e.g., this paper as a starting point).
Usually, the model is somewhat different than what you suggest, since just having an infinite alphabet is not very interesting, for the following reason:
Given an automaton with $n$ states, there are only $2^{n^2}$ transition matrices. Thus, if ...
Top 50 recent answers are included
