Distinguishability Operations and Closures

• Autorzy: Câmpeanu C. , Moreira N. , Reis R.

Identyfikatory

DOI

10.3233/FI-2016-1434

• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

formal languages; Myhill-Nerode relations; quotients; language operation; closures; regular languages; state complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 148, nr 3/4
• Strony: 243--266
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Câmpeanu C.

• Department of Computer Science, The University of Prince Edward Island, Charlottetown, PE, Canada

autor

Moreira N.

• Centro de Matemática e Faculdade de Ciências da Universidade do Porto, 4169-007 Porto, Portugal

autor

Reis R.

• Centro de Matemática e Faculdade de Ciências da Universidade do Porto, 4169-007 Porto, Portugal

Bibliografia

• [1] Ginsburg S. On the Length of the Smallest Uniform Experiment which Distinguishes the Terminal States of a Machine. J ACM. 1958;5(3):266–280. doi: 10.1145/320932.320938.
• [2] Ginsburg S, Spanier E. Distinguishability of a Semi-group by a Machine. Proceedings of the American Mathematical Society. 1961;12(4):661–668.
• [3] Sempere JM. Learning Reversible Languages with Terminal Distinguishability. In: Sakakibara Y, Kobayashi S, Sato K, Nishino T, Tomita E, editors. Proc. 8th ICGI 2006. vol. 4201 of LNCS. Springer; 2006. p. 354–355.
• [4] Câmpeanu C. Cover Languages and Implementations. In: Konstantinidis S, editor. Proc. 18th CIAA. vol. 7982 of LNCS. Springer; 2013. p. 1. doi:10.1007/978-3-642-39274-0_1.
• [5] Câmpeanu C, Pǎun A. Counting the Number of Minimal DFCA Obtained by Merging States. Int. J. Found. Comput. Sci. 2003;14(6):995–1006. Available from: http://dx.doi.org/10.1142/S0129054103002138.
• [6] Restivo A, Vaglica R. A Graph Theoretic Approach to Automata Minimality. Theor Comput Sci. 2012; 429:282–291. doi: 10.1016/j.tcs.2011.12.049.
• [7] Blumer A, Blumer J, Haussler D, Ehrenfeucht A, Chen MT, Seiferas JI. The Smallest Automaton Recognizing the Subwords of a Text. Theor Comput Sci. 1985;40:31–55.
• [8] Demaine ED, Eisenstat S, Shallit J, Wilson DA. Remarks on Separating Words. In: Holzer M, Kutrib M, Pighizzini G, editors. Proc. 13th DCFS. vol. 6808 of LNCS. Springer; 2011. p. 147–157. doi: 10.1007/978-3-642-22600-7_12.
• [9] Câmpeanu C, Moreira N, Reis R. The Distinguishability Operation on Regular Languages. In: Bensch S, Freund R, Otto F, editors. Proc. 6th NCMA 2014. Oesterreichische Computer Gesellschaft; 2014. p.85–100.
• [10] Bell J, Brzozowski JA, Moreira N, Reis R. Symmetric Groups and Quotient Complexity of Boolean Operations. In: Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, editors. Proc. 41st ICALP. vol. 8573 of LNCS. Springer; 2014. p. 1–12. doi: 10.1007/978-3-662-43951-7_1.
• [11] Sakarovitch J. Elements of Automata Theory. Cambridge University Press; 2009. ISBN:0521844258, 9780521844253.
• [12] Yu S. Regular languages. In: Rozenberg G, Salomaa A, editors. Handbook of Formal Languages. vol. 1. Springer; 1997. p. 41–110.
• [13] Mohri M, Moreno P, Weinstein E. General Suffix Automaton Construction Algorithm and Space Bounds. Theor Comput Sci. 2009;410(37):3553–3562. doi: 10.1016/j.tcs.2009.03.034.
• [14] Câmpeanu C, Moreira N, Reis R. On the Dissimilarity Operation on Finite Languages. H. Bordihn, R. Freund, B. Nagy, and G. Vaszil (ed.). In: Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016). Ősterreichische Computer Gesellschaft, 2016;321:105–120. ISBN 978-3-903035-10-2.
• [15] Brzozowski JA, Tamm H. Theory of Átomata. In: Mauri G, Leporati A, editors. Proc. 15th DLT. vol. 6795 of LNCS. Springer; 2011. p. 105–116.
• [16] Brzozowski JA, Tamm H. Complexity of Atoms of Regular Languages. Int J Found Comput Sci. 2013;24(7):1009–1028. Available from: http://dx.doi.org/10.1142/S0129054113400285.
• [17] Brzozowski JA. In Search of Most Complex Regular Languages. Int J Found Comput Sci. 2013;24(6):691–708. Available from: http://dx.doi.org/10.1142/S0129054113400133.
• [18] Brzozowski JA, Jirásková G, Zou C. Quotient Complexity of Closed Languages. Theory Comput Syst. 2014;54(2):277–292. doi: 10.1007/s00224-013-9515-7.
• [19] Kuratowski C. Sur l’Operation A de l’Analysis Situs. Fund Math. 1922;3:182–199.
• [20] Brzozowski JA, Grant E, Shallit J. Closures in Formal Languages and Kuratowski’s Theorem. Int J Found Comput Sci. 2011;22(2):301–321. Available from: http://dx.doi.org/10.1142/S0129054111008052.
• [21] Champarnaud J, Dubernard J, Jeanne H, Mignot L. Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions. In: Dediu AH, Mart´ın-Vide C, Truthe B, editors. Proc. 7th LATA 2013. vol. 7810 of Lecture Notes in Computer Science. Springer; 2013. p. 202–213. Available from: http://dx.doi.org/10.1007/978-3-642-37064-9_19. doi: 10.1007/978-3-642-37064-9_19.
• [22] Holzer M, Jakobi S. Nondeterministic Biautomata and Their Descriptional Complexity. In: Jürgensen H, Reis R, editors. Proc. 15th DCFS 2013. vol. 8031 of Lecture Notes in Computer Science. Springer; 2013. p. 112–123. doi:10.1007/978-3-642-39310-5_12.
• [23] Klíma O, Polák L. On Biautomata. RAIRO - Theor Inf and Applic. 2012;46(4):573–592. Available from: http://dx.doi.org/10.1051/ita/2012014. doi:10.1051/ita/2012014.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).