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 (23)

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 ⋮ Commutative nilpotent transformation semigroups ⋮ 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»

This page was built for publication: On deterministic finite automata and syntactic monoid size