On deterministic finite automata and syntactic monoid size
type: Item
instance of: scholarly article
title: On deterministic finite automata and syntactic monoid size
zbMATH Open document ID: 1161.68536
author: Markus Holzer
author: Barbara König
published in: Theoretical Computer Science
publication date: 2005-01-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 2126131
zbMATH Keywords: Automata theory
zbMATH Keywords: Deterministic finite automata
zbMATH Keywords: Syntactic monoids
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.04.010
OpenAlex ID: W2022378152
cites work: Q5538132
cites work: Q3856819
cites work: Q4126563
cites work: Automata Studies. (AM-34)
cites work: Implementation and Application of Automata
cites work: New upper bounds for the greatest number of proper colorings of a (V,E)‐graph
cites work: Sur l'ordre maximum d'un élément dans le groupe $S_n$ des permutations
cites work: Ordre maximal d'un élément du groupe $S_n$ des permutations et «highly composite numbers»
cites work: Q5840116
cites work: Q3769981
cites work: An introduction to chromatic polynomials
cites work: A Remark on Stirling's Formula
cites work: Q3265658
cites work: On the maximal order in $S_n$ and $S*_n$
DOI: 10.1016/J.TCS.2004.04.010
Recommended article: Q4412117
Recommended article: Q4452075
Recommended article: Q4412581
Recommended article: Q3150248
Recommended article: Q4574994
Recommended article: Q4428062
Recommended article: Q3615306
Recommended article: Q2984653
Recommended article: Q3714484
Recommended article: Q5186741
description: scientific article; zbMATH DE number 2126131