Distinguishability operations and closures

DOI10.3233/FI-2016-1434MaRDI QIDQ4589234zbMATH OpenOpenAlexFDO

Authors Nelma Moreira, Rogério Reis, C. Câmpeanu

Publication date 9 November 2017

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0160

zbMATH Keywords

closuresformal languageslanguage operationsMyhill-Nerode relationsquotientsregular languagesstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Given a regular language $L$, we study the language of words $mathsfD(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. 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 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$.

Recommendations

• Quotient complexity of regular languages
• On the computational complexity of problems related to distinguishability sets
• Power, positive closure, and quotients on convex languages

Cited in

(8)

• On the computational complexity of problems related to distinguishability sets
• Closure properties and witness reduction
• On the decidability of infix inclusion problem
• On the decidability of infix inclusion problem
• On the difference set of two transductions
• Binary distinguishability operation
• Binary right-distinguishability operation
• State complexity of side and rim operations

This page was built for publication: Distinguishability operations and closures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589234)