Infinitary Axiomatization of the Equational Theory of Context-Free Languages

• Autorzy: Grathwohl N. B. B. , Henglein F. , Kozen D.

Identyfikatory

DOI

10.3233/FI-2017-1469

• Języki publikacji: EN

Abstrakty

EN

We give a natural complete infinitary axiomatization of the equational theory of the context-free languages, answering a question of Leiß (1992).

Słowa kluczowe

EN

context free languages; Kleene algebra; algebraically complete semirings; Conway semirings; μ-semiring

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 150, nr 3/4
• Strony: 241--257
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Grathwohl N. B. B.

• Department of Computer Science (DIKU), University of Copenhagen, Denmark

autor

Henglein F.

• Department of Computer Science (DIKU), University of Copenhagen, Denmark

autor

Kozen D.

• Department of Computer Science, Cornell University, USA

Bibliografia

• [1] Conway JH. Regular Algebra and Finite Machines, Chapman and Hall, 1971. ISBN: 0412106205.
• [2] Bloom SL, Ésik Z. Iteration Theories: The Equational Logic of Iterative Processes, Springer-Verlag, 1993. doi: 10.1007/978-3-642-78034-9.
• [3] Leiß H. Towards Kleene Algebra with Recursion, CSL ’91: Proceedings of the 5th Workshop on Computer Science Logic, Springer-Verlag, London, UK, 1992. doi:10.1007/bfb0023771.
• [4] Gruska J. A Characterization of Context-Free Languages, J. Comput. Syst. Sci., 1971 ; 5 (4): 353-364. doi: 10.1016/s0022-0000(71)80023-5.
• [5] Courcelle B. Equivalences and Transformations of Regular Systems - Applications to Recursive Program Schemes and Grammars, Theoretical Computer Science, 1986; 42: 1-122. doi: 10.1016/0304-3975(86)90050-2.
• [6] Ésik Z, Leiß H. Greibach Normal Form in Algebraically Complete Semirings, CSL ’02: Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, Springer-Verlag, London, UK, 2002. doi: 10.1007/3-540-45793-3_10.
• [7] Ésik Z, Leiß H. Algebraically Complete Semirings and Greibach Normal Form, Annals of Pure and Applied Logic, 2005; 133 (1-3): 173-203. doi: 10.1016/j.apal.2004.10.008.
• [8] Hopkins M. The Algebraic Approach I: The Algebraization of the Chomsky Hierarchy, Proc. 10th Int. Conf. Relational Methods in Computer Science and 5th Int. Conf. Applications of Kleene Algebra (RelMiCS/AKA 2008) (R. Berghammer, B. Möller, G. Struth, Eds.), 4988, Springer-Verlag, Berlin Heidelberg, April 2008. doi: 10.1007/978-3-540-78913-0_13.
• [9] Hopkins M. The Algebraic Approach II: Dioids, Quantales and Monads, Proc. 10th Int. Conf. Relational Methods in Computer Science and 5th Int. Conf. Applications of Kleene Algebra (RelMiCS/AKA 2008) (R. Berghammer, B. Möller, G. Struth, Eds.), 4988, Springer-Verlag, Berlin Heidelberg, April 2008. doi: 10.1007/978-3-540-78913-0_14.
• [10] Ésik Z, Kuich W. Modern Automata Theory, 2007, Unpublished manuscript.
• [11] Barendregt H. The Lambda Calculus: Its Syntax and Semantics, vol. 103 of Studies in Logic and the Foundations of Mathematics, North-Holland, 1984. ISBN: 978-0444875082.
• [12] Ésik Z. Completeness of Park induction, Theoretical Computer Science, 1997; 177 ( 1 ): 217-283. doi: 10.1016/s0304-3975(96)00240-x.
• [13] Park DMR. Fixpoint Induction and Proofs of Program Properties, Machine Intelligence (D. Michie. B. Meltzer, Eds.), 5, Edinburgh University Press, 1969, pp. 59-78.
• [14] Bekić H. Definable Operations in General Algebras, and the Theory of Automata and Flowcharts, in: Programming Languages and Their Definition (C. Jones, Ed.), vol. 177 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1984, pp. 30-55. doi: 10.1007/BFb0048939.
• [15] Winskel G. The Formal Semantics of Programming Languages, MIT Press, 1993. ISBN: 0-262-23169-7.
• [16] Kozen D. The Design and Analysis of Algorithms, Springer-Verlag, New York, 1991. ISBN-10: 0387976876, 13: 978-0387976877.
• [17] Kozen D. Results on the Prepositional μ-calculus, Theoretical Computer Science, 1983; 27 (3): 333-354. doi: 10.1016/0304-3975(82)90125-6.
• [18] Kozen D. On Induction vs. *-Continuity, Proc. Logics of Programs, Lecture Notes in Computer Science 131, pp. 167-176. Springer, May 1981. doi: 10.1007/bfb0025782.
• [19] Kozen D. Automata and Computability, Undergraduate Texts in Computer Science, Springer New York, 1997. doi: 10.1007/978-1-4612-1844-9.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).