nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

The Power of Programs over Monoids in J

verfasst von : Nathan Grosshans

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

The model of programs over (finite) monoids, introduced by Barrington and Thérien, gives an interesting way to characterise the circuit complexity class

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-40608-0_22/492458_1_En_22_IEq1_HTML.gif

and its subclasses and showcases deep connections with algebraic automata theory. In this article, we investigate the computational power of programs over monoids in

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-40608-0_22/492458_1_En_22_IEq2_HTML.gif

, a small variety of finite aperiodic monoids. First, we give a fine hierarchy within the class of languages recognised by programs over monoids from

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-40608-0_22/492458_1_En_22_IEq3_HTML.gif

, based on the length of programs but also some parametrisation of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-40608-0_22/492458_1_En_22_IEq4_HTML.gif

. Second, and most importantly, we make progress in understanding what regular languages can be recognised by programs over monoids in

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-40608-0_22/492458_1_En_22_IEq5_HTML.gif

. We show that those programs actually can recognise all languages from a class of restricted dot-depth one languages, using a non-trivial trick, and conjecture that this class suffices to characterise the regular languages recognised by programs over monoids in

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-40608-0_22/492458_1_En_22_IEq6_HTML.gif

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 The Automatic Baire Property and an Effective Property of -Rational Functions

Nächstes Kapitel Geometrically Closed Positive Varieties of Star-Free Languages

Ajtai, M.: \({\Sigma }_{1}^{1}\)-formulae on finite structures. Ann. Pure Appl. Logic 24(1), 1–48 (1983)

Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC\({^1}\). J. Comput. Syst. Sci. 38(1), 150–164 (1989)MathSciNetCrossRef

Barrington, D.A.M., Thérien, D.: Finite monoids and the fine structure of NC\({^1}\). J. ACM 35(4), 941–952 (1988)MathSciNetCrossRef

Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press, New York (1974)MATH

Eilenberg, S.: Automata, Languages, and Machines, vol. B. Academic Press, New York (1976)MATH

Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13–27 (1984)MathSciNetCrossRef

Grosshans, N.: The limits of Nečiporuk’s method and the power of programs over monoids taken from small varieties of finite monoids. Ph.D. thesis, University of Paris-Saclay, France (2018)

Grosshans, N., McKenzie, P., Segoufin, L.: The power of programs over monoids in DA. In: MFCS 2017, Aalborg, Denmark, 21–25 August 2017, pp. 2:1–2:20 (2017)

Klíma, O., Polák, L.: Hierarchies of piecewise testable languages. Int. J. Found. Comput. Sci. 21(4), 517–533 (2010)MathSciNetCrossRef

10.

Lautemann, C., Tesson, P., Thérien, D.: An algebraic point of view on the Crane Beach property. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 426–440. Springer, Heidelberg (2006). https://doi.org/10.1007/11874683_28CrossRef

11.

Maciel, A., Péladeau, P., Thérien, D.: Programs over semigroups of dot-depth one. Theor. Comput. Sci. 245(1), 135–148 (2000)MathSciNetCrossRef

12.

McKenzie, P., Péladeau, P., Thérien, D.: NC\({^1}\): the automata-theoretic viewpoint. Comput. Complex. 1, 330–359 (1991)MathSciNetCrossRef

13.

Péladeau, P.: Classes de circuits booléens et variétés de monoïdes. Ph.D. thesis, Université Pierre-et-Marie-Curie (Paris-VI), Paris, France (1990)

14.

Péladeau, P., Straubing, H., Thérien, D.: Finite semigroup varieties defined by programs. Theor. Comput. Sci. 180(1–2), 325–339 (1997)MathSciNetCrossRef

15.

Pin, J.: The dot-depth hierarchy, 45 years later. In: The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, pp. 177–202 (2017)

16.

Pin, J.: Varieties of Formal Languages. Plenum Publishing Co., New York (1986)CrossRef

17.

Pin, J., Straubing, H.: Some results on \(\cal{C}\)-varieties. ITA 39(1), 239–262 (2005)MathSciNetMATH

18.

Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 214–222. Springer, Heidelberg (1975). https://doi.org/10.1007/3-540-07407-4_23CrossRef

19.

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

20.

Straubing, H.: When can one finite monoid simulate another? In: Birget, J.C., Margolis, S., Meakin, J., Sapir, M. (eds.) Algorithmic Problems in Groups and Semigroups, pp. 267–288. Springer, Boston (2000). https://doi.org/10.1007/978-1-4612-1388-8_15CrossRef

21.

Straubing, H.: Languages defined with modular counting quantifiers. Inf. Comput. 166(2), 112–132 (2001)MathSciNetCrossRef

22.

Tesson, P.: Computational complexity questions related to finite monoids and semigroups. Ph.D. thesis, McGill University, Montreal (2003)

23.

Tesson, P., Thérien, D.: The computing power of programs over finite monoids. J. Autom. Lang. Comb. 7(2), 247–258 (2001)MathSciNetMATH

Titel: The Power of Programs over Monoids in J
verfasst von: Nathan Grosshans
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_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"