On deterministic finite automata and syntactic monoid size (Q703576): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
| Property / DOI | |||
| Property / DOI: 10.1016/j.tcs.2004.04.010 / rank | |||
| Property / DOI | |||
| Property / DOI: 10.1016/J.TCS.2004.04.010 / rank | |||
Normal rank | |||
Revision as of 07:28, 9 December 2024
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
