nach oben

Theory of Computing Systems

Erschienen in:

08.11.2018

A Unifying Approach to Algebraic Systems Over Semirings

verfasst von: Peter Kostolányi

Erschienen in: Theory of Computing Systems | Ausgabe 3/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A fairly general definition of canonical solutions to algebraic systems over semirings is proposed. This is based on the notion of summation semirings, traditionally known as \({\Sigma }\)-semirings, and on assigning unambiguous context-free languages to variables of each system. The presented definition applies to all algebraic systems over continuous or complete semirings and to all proper algebraic systems over power series semirings, for which it coincides with the usual definitions of their canonical solutions. As such, it unifies the approaches to algebraic systems over semirings studied in literature. An equally general approach is adopted to study pushdown automata, for which equivalence with algebraic systems is proved. Finally, the Chomsky-Schützenberger theorem is generalised to the setting of summation semirings.

Vorheriger Artikel On the Parameterized Complexity of Contraction to Generalization of Trees

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 "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

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

To be more precise, weighted context-free grammars over complete semirings are considered in [6]. These can nevertheless be viewed as algebraic systems.

We shall dispense with a formally defined notion of weighted context-free grammars over semirings. Nevertheless, an idea of such grammars is useful for gaining intuition.

Semiring-polynomials can be introduced as a specialisation of the notion of polynomials over a universal algebra [16]. With this definition, a semiring-polynomial can be seen as a congruence class of a suitable congruence defined on the algebra of representations of semiring-polynomials as defined below. However, let us stress that this distinction is unimportant for our purposes, since similarly as in [9], we shall only be interested in mappings induced by (representations of) semiring-polynomials.

Note that the resulting algebra is not a semiring. On the other hand, the algebra of semiring-polynomials, which can be obtained as a factor algebra of the algebra of their representations, constitutes a semiring [16].

Commutativity of S is a commonplace assumption when dealing with algebraic systems over S〈〈Σ^∗〉〉 [17, 19]. However, let us note that it is not strictly necessary [17] and that the approach presented later in this article subsumes the noncommutative case as well.

This generalised partition can be of any cardinality, as \((0 ~|~ i \in I^{\prime })\) is in \(\mathcal {F}\) for any \(I^{\prime }\).

More precisely, we should write \(m^{\prime } = \{c_{m,0}\} y_{1} \{c_{m,1}\} {\ldots } \{c_{m,r-1}\}y_{r} \{c_{m,r}\}\). However, we follow here the common practice of identifying a singleton set \(\{c\}\) with c itself.

The polynomials of a template system will in fact all be \(2_{1}^{\Sigma }\)-polynomials. However, the sets \(\emptyset \) and \(\{\varepsilon \}\) are the zero and the unity in the semiring \(2^{{\Sigma }^{*}}\), so they have to be included in order to satisfy the technical condition imposed in Definition 3.

Droste and Vogler [6] have in fact dealt with grammars over valuation monoids, thus going beyond semirings.

Here, N stands for a nonempty finite alphabet of nonterminals, \({\Sigma }\) stands for a nonempty finite alphabet of terminals, \(N \cap {\Sigma } = \emptyset \), \(P \subseteq N \times (N \cup T)^{*}\) is a set of production rules, and \(\sigma \) in N is the initial nonterminal.

For the sake of correctness, let us note that the following definition is sound only because it is consistent with the usual definition for automata over semirings of formal languages. This is a hidden proposition, which is nevertheless easy to prove.

Bloom, S.L., Ésik, Z., Kuich, W.: Partial conway and iteration semirings. Fundam. Inform. 86, 19–40 (2008)MathSciNetMATH

Chomsky, N., Schützenberger, M.-P.: The algebraic theory of context-free languages. In: Braffort, P., Hirschberg, D. (eds.) Computer programming and formal systems, pp. 118-161. North Holland, Amsterdam (1963)

Davey, B.A., Priestley, H.A.: Introduction to lattices and order 2nd ed. Cambridge University Press, Cambridge (2002)CrossRefMATH

Droste, M., Kuich, W., Vogler, H.: Handbook of weighted automata. Springer, Berlin (2009)CrossRefMATH

Droste, M., Kuich, W.: Semirings and Formal Power Series. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of weighted automata. Monographs in theoretical computer science, pp 3–28. Springer, Berlin (2009)

Droste, M., Vogler, H.: The chomsky-schützenberger theorem for quantitative context-free languages. Int. J. Found. Comput. Sci. 25, 955–970 (2014)CrossRefMATH

Ésik, Z., Kuich, W.: A unifying kleene theorem for weighted finite automata. In: Calude, C. S., Rozenberg, G., Salomaa, A. (eds.) Maurer Festschrift. LNCS, vol. 6570, pp 76–89. Springer, Berlin Heidelberg (2011)

Ésik, Z., Kuich, W.: Inductive *-Semirings. Theor. Comput. Sci. 324, 3–33 (2004)MathSciNetCrossRefMATH

Ésik, Z., Kuich, W.: Modern automata theory. http://www.dmg.tuwien.ac.at/kuich/mat.pdf

10.

Hebisch, U., Weinert, H.J.: Semirings – algebraic theory and applications in computer science. World Scientific, Singapore (1998)CrossRefMATH

11.

Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley, Reading (1979)MATH

12.

Korenjak, A.J., Hopcroft, J.E.: Simple deterministic languages. In: SWAT 1966, pp 36–46. IEEE Computer Society, Washington (1966)

13.

Kostolányi, P., Rovan, B.: Automata with auxiliary weights. Int. J. Found. Comput. Sci. 27, 787–807 (2016)MathSciNetCrossRefMATH

14.

Kuich, W.: Semirings and formal power series: their relevance to formal languages and automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of formal languages, vol. 1, pp 609–677. Springer, Berlin (1997)

15.

Kuich, W., Salomaa, A.: Semirings, automata, languages. Springer, Berlin (1986)CrossRefMATH

16.

Lausch, H., Nöbauer, W.: Algebra of polynomials. North Holland, Amsterdam (1973)

17.

Petre, I., Salomaa, A.: Algebraic systems and pushdown automata. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of weighted automata. Monographs in theoretical computer science, pp 257–289. Springer, Berlin (2009)

18.

Sakarovitch, J.: Elements of automata theory. Cambridge University Press, Cambridge (2009)CrossRefMATH

19.

Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series. Springer, New York (1978)CrossRefMATH

20.

Stanat, D.F.: A homomorphism theorem for weighted context-free grammars. J. Comput. Syst. Sci. 6, 217–232 (1972)MathSciNetCrossRefMATH

Titel: A Unifying Approach to Algebraic Systems Over Semirings
verfasst von: Peter Kostolányi
Publikationsdatum: 08.11.2018
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 3/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9895-9

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2019

Better Complexity Bounds for Cost Register Automata

On the Parameterized Complexity of Contraction to Generalization of Trees

Property Testing Lower Bounds via a Generalization of Randomized Parity Decision Trees

Computing Parameters of Sequence-Based Dynamic Graphs

Capturing Points with a Rotating Polygon (and a 3D Extension)

Pattern Matching and Consensus Problems on Weighted Sequences and Profiles