On deterministic finite automata and syntactic monoid size

DOI10.1016/j.tcs.2004.04.010zbMath1161.68536OpenAlexW2022378152MaRDI QIDQ703576

Barbara König, Markus Holzer

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.04.010

zbMATH Keywords

Automata theoryDeterministic finite automataSyntactic monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

State complexity of permutation on finite languages over a binary alphabet, Representation of (Left) Ideal Regular Languages by Synchronizing Automata, Syntactic complexity of bifix-free languages, Green's relations in finite transformation semigroups, Complexity of suffix-free regular languages, On the size of inverse semigroups given by generators, Syntactic complexity of suffix-free languages, Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages, Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages, SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES, Syntactic complexity of regular ideals, Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages, State complexity of deletion and bipolar deletion, Most Complex Non-Returning Regular Languages, Complexity of proper prefix-convex regular languages, Complexity of proper prefix-convex regular languages, The complexity of weakly recognizing morphisms, Green's relations in deterministic finite automata, Operations on Weakly Recognizing Morphisms, Syntactic complexity of bifix-free regular languages, Descriptional complexity of regular languages, Generalized Post embedding problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Remark on Stirling's Formula
• Automata Studies. (AM-34)
• On the maximal order in $S_n$ and $S*_n$
• New upper bounds for the greatest number of proper colorings of a (V,E)‐graph
• Implementation and Application of Automata
• An introduction to chromatic polynomials
• Sur l'ordre maximum d'un élément dans le groupe $S_n$ des permutations
• Ordre maximal d'un élément du groupe $S_n$ des permutations et «highly composite numbers»