# Questions tagged [automata-theory]

The tag has no usage guidance.

101 questions
Filter by
Sorted by
Tagged with
555 views

### Origin of tropical mathematics

On Wikipedia, it is claimed without a source that Imre Simon founded tropical mathematics. The first work of his I was able to find on the subject is Limited subsets of a free monoid which uses the ...
• 191
34 views

### A particular generalization of free partially commutative monoids

A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
• 21
1 vote
56 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 ...
51 views

### First-order logics expressively equivalent to the computable languages

There is a really nice theorem that the subsets of $(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$ definable in first-order logic are exactly the regular sets. Where: $\Sigma^*$ is the set of ...
• 359
134 views

### Corollaries of Kleene's Theorem (Regular Languages)

Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the ...
• 359
107 views

### Are "germ" automata studied?

I've been exploring the idea of a nondeterministic continuous automaton based on germs: Two functions $f,g: \mathbb{R} \to S$ have the same right germ at $x$ if there is some interval $[x,a)$ on which ...
• 359