LIPIcs.CSL.2016.6.pdf
- Filesize: 463 kB
- 15 pages
Document
The Matrix Ring of a mu-Continuous Chomsky Algebra is mu-Continuous
Author
-
Part of:
Volume:
25th EACSL Annual Conference on Computer Science Logic (CSL 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-29
Cite AsGet BibTex
Hans Leiss. The Matrix Ring of a mu-Continuous Chomsky Algebra is mu-Continuous. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CSL.2016.6
https://doi.org/10.4230/LIPIcs.CSL.2016.6
Abstract
In the course of providing an (infinitary) axiomatization of the equational theory of the class of context-free languages, Grathwohl, Kozen and Henglein (2013) have introduced the class of mu-continuous Chomsky algebras. These are idempotent semirings where least solutions for systems of polynomial inequations (i.e. context-free grammars) can be computed iteratively and where multiplication is continuous with respect to the least fixed point operator mu. We prove that the matrix ring of a mu-continuous Chomsky algebra also is a mu-continuous Chomsky algebra.
Keywords
- context-free language
- fixed point operator
- idempotent semiring
- matrix ring
- Chomsky algebra
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Hans Bekić. Definable operations in general algebras, and the theory of automata and flowcharts. In C. B. Jones, editor, Programming Languages and Their Definition, volume 177 of LNCS, pages 30-55. Springer-Verlag, Berlin Heidelberg, 1984.
-
J. H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, London, 1971.
-
J.W. de Bakker and D. Scott. A theory of programs. IBM Seminar, Vienna, 1969.
-
J. Gruska. A characterization of context-free languages. Journal of Computer and System Sciences, 5:353-364, 1971.
-
Mark Hopkins. The algebraic approach I: The algebraization of the Chomsky hierarchy. In 10th Int. Conf. on Relational Methods in Computer Science and 5th Int. Conf. on Applications of Kleene Algebra, volume 4988 of LNCS, pages 155-172. Springer-Verlag, Berlin Heidelberg, 2008.
-
Mark Hopkins. The algebraic approach II: The algebraization of the Chomsky hierarchy. In 10th Int. Conf. on Relational Methods in Computer Science and 5th Int. Conf. on Applications of Kleene Algebra, volume 4988 of LNCS, pages 173-190. Springer-Verlag, Berlin Heidelberg, 2008.
-
Dexter Kozen. Results in the propositional μ-calculus. Theoretical Computer Science, 27(3):333-345, 1983.
-
Dexter Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. In 6th Annual Symposium on Logic in Computer Science, July 15-18, 1991, Amsterdam, Los Alamitos, CA, 1991. Computer Society Press.
-
H. Leiß. Towards Kleene Algebra with Recursion. In E. Börger, G. Jäger, H. Kleine-Büning, and M. M. Richter, editors, CSL'91. 5th Workshop on Computer Science Logic. Berne, Switzerland, October 7-11, 1991, pages 242-256. Springer LNCS 626, 1991.
-
Hans Leiß and Zoltan Ésik. Algebraically complete semirings and Greibach normal form. Annals of Pure and Applied Logic, 133:173-203, 2005.
- Niels Bjørn Bugge Grathwohl, Fritz Henglein, and Dexter Kozen. Infinitary axiomatization of the equational theory of context-free languages. In D. Baelde and A. Carayol, editors, Fixed Points in Computer Science (FICS 2013), volume 126 of EPTCS, pages 44-55, 2013. URL: http://dx.doi.org/10.4204/EPTCS.126.4.