Closures in Formal Languages: Concatenation, Separation, and Algorithms

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
submitted to DLT 2009

Keywords

Computational Complexity, Formal Languages and Automata Theory

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/226374

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0901.3763
 http://arxiv.org/abs/0901.3763

Collections

arXiv