2009/12/05 by Janusz Brzozowski, J. Brzozowski, Galina Jirásková +3 · 2 citations
Computer Science · Mathematics · #Abstract family of languages #Advanced Algebra and Logic #Algorithm #Arithmetic #Automaton #Closure (psychology) #Combinatorics #Complement (music) #Computer science #Concatenation (mathematics) #Discrete mathematics #Formal language #Linguistics #Mathematics #Natural Language Processing Techniques #Prefix #Programming language #Quotient #Regular language #Suffix #Theoretical computer science #Transitive closure #Word (group theory) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.1007/978-3-642-13182-0_8
12 pages, 5 eps figures, uses llncs
arxiv created 2009/12/05 · openalex publication_date 2010/01/01 · arxiv updated 2015/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in the same way, where by subword we mean subsequence. We study the quotient complexity (usually called state complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the prefix-, suffix-, factor-, and subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star and reversal in each of the four classes of closed languages. We show that repeated application of positive closure and complement to a closed language results in at most four distinct languages, while Kleene closure and complement gives at most eight languages.