## New answers tagged automata-theory

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

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

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

Top 50 recent answers are included

#### Related Tags

automata-theory × 107formal-languages × 41

computer-science × 22

lo.logic × 18

co.combinatorics × 13

gr.group-theory × 13

reference-request × 9

computability-theory × 8

graph-theory × 7

computational-complexity × 7

semigroups-and-monoids × 7

geometric-group-theory × 6

decidability × 6

lambda-calculus × 5

ct.category-theory × 4

nt.number-theory × 3

pr.probability × 3

soft-question × 3

algorithms × 3

model-theory × 3

markov-chains × 3

combinatorial-group-theory × 3

cellular-automata × 3

ho.history-overview × 2

terminology × 2