nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Geometrical Closure of Binary \(V_{3/2}\) Languages

verfasst von : Jean-Philippe Dubernard, Giovanna Guaiana, Ludovic Mignot

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We define the geometrical closure of a language over a \(j\)-ary alphabet, and we prove that in the case of dimension 2 the family \(V_{3/2}\) in the Straubing-Thérien hierarchy of languages is closed under this operation. In other words, the geometrical closure of a \(V_{3/2}\) binary language is still a \(V_{3/2}\) language. This is achieved by carrying out some transformations over a regular expression representing the \(V_{3/2}\) language, which leads to a \(V_{3/2}\) regular expression for the geometrical closure.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Toroidal Codes and Conjugate Pictures

Nächstes Kapitel Deterministic Biautomata and Subclasses of Deterministic Linear Languages

Arfi, M.: Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91(1), 71–84 (1991)MathSciNetCrossRef

Baruah, S.K., Rosier, L.E., Howell, R.R.: Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Syst. 2(4), 301–324 (1990)CrossRef

Béal, M.-P., Champarnaud, J.-M., Dubernard, J.-P., Jeanne, H., Lombardy, S.: Decidability of geometricity of regular languages. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 62–72. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31653-1_7CrossRef

Blanpain, B., Champarnaud, J.M., Dubernard, J.P.: Geometrical languages. In: LATA, Report 35/07, pp. 127–138. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona (2007)

Bouajjani, A., Muscholl, A., Touili, T.: Permutation rewriting and algorithmic verification. Inf. Comput. 205(2), 199–224 (2007)MathSciNetCrossRef

Champarnaud, J.-M., Dubernard, J.-P., Jeanne, H.: Geometricity of binary regular languages. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 178–189. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13089-2_15CrossRef

Geniet, D., Largeteau, G.: WCET free time analysis of hard real-time systems on multiprocessors: a regular language-based model. Theoret. Comput. Sci. 388(1–3), 26–52 (2007)MathSciNetCrossRef

Guaiana, G., Restivo, A., Salemi, S.: On the trace product and some families of languages closed under partial commutations. J. Automata Lang. Comb. 9(1), 61–79 (2004)MathSciNetMATH

Largeteau, G., Geniet, D., Andrès, É.: Discrete geometry applied in hard real-time systems validation. In: Andres, E., Damiand, G., Lienhardt, P. (eds.) DGCI 2005. LNCS, vol. 3429, pp. 23–33. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31965-8_3CrossRefMATH

10.

Mignot, L.: Application: geometrical closure of \(V_{3/2}\) binary expressions. http://ludovicmignot.free.fr/programmes/geomClosure/index.html. Accessed 27 Oct 2018

11.

Pin, J.É.: The dot-depth hierarchy, 45 years later. In: The Role of Theory in Computer Science, pp. 177–202. World Scientific (2017)

12.

Pin, J.É., Weil, P.: Ponynominal closure and unambiguous product. Theory Comput. Syst. 30(4), 383–422 (1997)MathSciNetCrossRef

13.

Place, T., Zeitoun, M.: Concatenation hierarchies: new bottle, old wine. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 25–37. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58747-9_5CrossRef

14.

Place, T., Zeitoun, M.: Generic results for concatenation hierarchies. Theory Comput. Syst. 1–53 (2017). https://doi.org/10.1007/s00224-018-9867-0

15.

Straubing, H.: Finite semigroup varieties of the form \(v * d\). J. Pure Appl. Algebra 36, 53–94 (1985)MathSciNetCrossRef

16.

Thérien, D.: Classification of finite monoids: the language approach. Theoret. Comput. Sci. 14, 195–208 (1981)MathSciNetCrossRef

Titel: Geometrical Closure of Binary Languages
verfasst von: Jean-Philippe Dubernard
Giovanna Guaiana
Ludovic Mignot
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-13434-1

Electronic ISBN: 978-3-030-13435-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-13435-8_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"