New answers tagged

4 votes
Accepted

Understanding Syntactic Congruence & Order

If you have the minimal automaton, then two words are syntactically equivalent iff from any give state they lead to the same state. Therefore the syntactic monoid is the monoid generated by the ...
Benjamin Steinberg's user avatar
1 vote

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$?

I'm posting a new answer because I think the discussion on my previous answer is helpful for understanding the edits to the question, and what I'm adding here is a complete rewrite and is much too ...
Sophie M's user avatar
  • 685
0 votes

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$?

I believe the answer to Question 1 is positive, though maybe I've misunderstood something and the following sketch misses something important. For $n \in [1,N]$, the DFA halts and decides whether $n \...
Sophie M's user avatar
  • 685

Top 50 recent answers are included