2014/03/09 by Janusz Brzozowski, Brzozowski, Janusz, Marek Szykuła +1 · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Automaton #Cardinality (data modeling) #Combinatorics #Computability, Logic, AI Algorithms #Computer science #Discrete mathematics #Ideal (ethics) #Linguistics #Mathematics #Quotient #Regular language #Semigroup #Suffix #Theoretical computer science #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1403.2090
15 pages, 7 figures
openalex publication_date 2014/03/09 · arxiv created 2014/07/03 · arxiv updated 2014/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We solve two open problems concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a left ideal or a suffix-closed language with n left quotients (that is, with state complexity n) is at most nn-1+n-1, and that of a two-sided ideal or a factor-closed language is at most nn-2+(n-2)2n-2+1. Since these bounds are known to be reachable, this settles the problems.