Some remarks on the orbit of closure-involution operations on languages. (English) Zbl 1518.68165
Summary: For a closure operation \(c\) and an involution \(i\) defined on a language family \(\mathcal{M} \), we define \(\mathcal{N}_{c , i}^{\mathcal{M}}(L)\) as the number of distinct languages which can be obtained from a language \(L\) by repeated applications of \(c\) and \(i\). The orbit \(\mathcal{O}^{\mathcal{M}}(c, i)\) of \(c\) and \(i\) is defined as the set of all these numbers.
We show that for the families of all languages and all regular languages over some alphabet and some classical closure operators \(c\) on languages, there are involutions \(i\) such that the orbit \(\mathcal{O}^{\mathcal{M}}(c, i)\) contains arbitrary large numbers or contains infinity (which is in contrast to Kuratowski’s complement-closure theorem). Moreover, we show that it is undecidable whether infinity occurs in the orbit.
We show that for the families of all languages and all regular languages over some alphabet and some classical closure operators \(c\) on languages, there are involutions \(i\) such that the orbit \(\mathcal{O}^{\mathcal{M}}(c, i)\) contains arbitrary large numbers or contains infinity (which is in contrast to Kuratowski’s complement-closure theorem). Moreover, we show that it is undecidable whether infinity occurs in the orbit.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Brzozowski, J.; Grant, E.; Shallit, J., Closures in formal languages and Kuratowski’s theorem, Int. J. Found. Comput. Sci., 22, 301-321 (2011) · Zbl 1246.68139 |
| [2] | Charlier, É.; Domaratzki, M.; Harju, T.; Shallit, J., Composition and orbits of languages: finiteness and upper bounds, Int. J. Comput. Math., 90, 1171-1196 (2013) · Zbl 1361.68119 |
| [3] | Dassow, J., On the orbit of closure-involution operations - the case of formal languages, Theor. Comput. Sci., 777, 192-203 (2019) · Zbl 1439.68013 |
| [4] | Gardner, B. J.; Jackson, M., The Kuratowski closure-complement theorem, N.Z. J. Math., 38, 9-44 (2008) · Zbl 1185.54002 |
| [5] | Hammer, D. H., Kuratowski’s closure theorem, Nieuw Arch. Wiskd., 7, 74-80 (1960) · Zbl 0137.15503 |
| [6] | Kuratowski, C., Sur l’opération \(\overline{A}\) de l’analysis situs, Fundam. Math., 3, 182-199 (1922) · JFM 48.0210.04 |
| [7] | Peleg, D., A generalized closure and complement phenomenon, Discrete Math., 50, 285-293 (1984) · Zbl 0542.54001 |
| [8] | Rozenberg, G.; Salomaa, A., Handbook of Formal Languages (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0866.68057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
