2009/01/23 by J. Brzozowski, Janusz Brzozowski, Brzozowski, J. +6
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #cs.CC #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0901.3763
submitted to DLT 2009
arxiv created 2009/01/23 · openalex publication_date 2009/01/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We continue our study of open and closed languages. We investigate how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the separation axioms in topological spaces; one of our main results is that there is a clopen partition separating two words if and only if the words commute. We show that we can decide in quadratic time if the language specified by a DFA is closed, but if the language is specified by an NFA, the problem is PSPACE-complete.