On deterministic finite automata and syntactic monoid size (Q703576): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.tcs.2004.04.010 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2022378152 / rank | |||
Normal rank | |||
Revision as of 23:34, 19 March 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
