Closures in Formal Languages: Concatenation, Separation, and Algorithms

Simple item page
dc.creatorBrzozowski, J.
dc.creatorGrant, E.
dc.creatorShallit, J.
dc.date2009-01-23
dc.date.accessioned2026-07-07T13:02:13Z
dc.date.available2026-07-07T13:02:13Z
dc.descriptionWe 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.
dc.descriptionsubmitted to DLT 2009
dc.identifierhttps://arxiv.org/abs/0901.3763
dc.identifierhttp://arxiv.org/abs/0901.3763
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/226374
dc.subjectComputational Complexity
dc.subjectFormal Languages and Automata Theory
dc.titleClosures in Formal Languages: Concatenation, Separation, and Algorithms
dc.typetext

Files

Collections

arXiv