Distinguishability Operations and Closures

• Tipo: Artigo em Revista Científica Internacional
• Data: 2016

Autores

Campeanu, C (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

Título: Fundamenta Informaticae

Vol. 148

Páginas: 243-266

ISSN: 0169-2968

Editora: IOS PRESS

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 6 Citações

Outras Informações

ID Authenticus: P-00M-AMF

DOI: 10.3233/fi-2016-1434

Abstract (EN): Given a language L, we study the language of words D (L), that distinguish between pairs of different left quotients of L. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. For the case of regular languages, we give an upper bound for the state complexity of the distinguishability operation, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different left quotients of a regular language L has at most n - 1 elements, where n is the state complexity of L, and we also study the properties of its iteration. We generalize the results for the languages of words that distinguish between pairs of different right quotients and two-sided quotients of a language L.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 24