On deterministic finite automata and syntactic monoid size (Q703576)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On deterministic finite automata and syntactic monoid size |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On deterministic finite automata and syntactic monoid size |
scientific article |
Statements
On deterministic finite automata and syntactic monoid size (English)
0 references
11 January 2005
0 references
We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of \(n\)-state (minimal) deterministic finite automata. We show tight upper and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used. It turns out, that the two generator case is the most involved one.
0 references
Automata theory
0 references
Deterministic finite automata
0 references
Syntactic monoids
0 references
0 references
0 references
