Algebraic theories (Kleene algebra; context-free languages)

Books and Proceedings

1. Masaru Tomita. Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers, 1985.
2. J. Hopcroft, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

Academic Journals

1. Claus Brabrand, Robert Giegerich, Anders Möller. Analyzing Ambiguity of Context-Free Grammars. Science of Computer Programming, To appear. Earlier version in Proc.\ 12th International Conference on Implementation and Application of Automata, CIAA\ '07, Springer-Verlag LNCS vol.\ 4783, 75(3), 2010.
2. J. Engelfriet, S. Maneth, H. Seidl. Deciding equivalence of top-down XML transformations in polynomial time. Journal of Computer and System Sciences, 75(5):271-286, 2009.
3. Hans Hüttel, Naoki Kobayashi, Takashi Suto. Undecidable equivalences for basic parallel processes. Information and Computation, 207(7):812-829, 2009.
4. A. Frisch, G. Castagna, V. Benzaken. Semantic subtyping: dealing set-theoretically with function, union, intersection, and negation types. Journal of the ACM (JACM), 55(4), 2008.
5. M. Hopkins. The Algebraic Approach II: Dioids, Quantales and Monads. Lecture Notes in Computer Science, 4988, 2008.
6. M. Hopkins. The Algebraic Approach I: The Algebraization of the Chomsky Hierarchy. Lecture Notes in Computer Science, 4988, 2008.
7. B. Ktari, F. Lajeunesse-Robert, C. Bolduc. Solving Linear Equations in\^*-continuous Action Lattices. Lecture Notes in Computer Science, 4988, 2008.
8. Claus Brabrand, Anders Möller, Michael I. Schwartzbach. Dual Syntax for XML Languages. Information Systems, Earlier version in Proc. 10th International Workshop on Database Programming Languages, DBPL\ '05, Springer-Verlag LNCS vol.\ 3774, 33(4), June 2008.
9. J.N. Foster, M.B. Greenwald, J.T. Moore, B.C. Pierce, A. Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 29(3), 2007.
10. J. Desharnais, B. Möller, G. Struth. Kleene algebra with domain. ACM Transactions on Computational Logic (TOCL), 7(4):798-833, 2006.
11. Martin Sulzmann, Kenny Zhuo Ming Lu. A Type-Safe Embedding of XDuce into ML. Electronic Notes in Theoretical Computer Science, Proceedings of the ACM-SIGPLAN Workshop on ML (ML 2005). ISSN: 1571-0661, 148(2):239-264, 2006.
12. Hans Lei\ss. Kleene modules and linear languages. Journal of Logic and Algebraic Programming, Relation algebra and Kleene algebra, 66(2):185-194, 2006.
13. Jiri Adamek, Stefan Milius, Jiri Velebil. Iterative algebras at work. Mathematical Structures in Computer Science (MSCS), 16:1085-1131, 2006.
14. Haruo Hosoya, Jerome Vouillon, Benjamin C. Pierce. Regular expression types for XML. ACM Trans. Program. Lang. Syst, 27(1):46-90, 2005. download
15. Jan J. M. M. Rutten. A tutorial on coinductive stream calculus and signal flow graphs. Theor. Comput. Sci, 343(3):443-481, 2005.
16. Luca Aceto, Zolt\'an Ésik, Anna Ingólfsdóttir. Equational theories of tropical semirings. Theoretical Computer Science, Foundations of Software Science and Computation Structures, 298(3):417-469, 2003.
17. Luigi Santocanale. On the equational definition of the least prefixed point. Theoretical Computer Science, 295(1):341-370, 2003.
18. J.J.M.M. Rutten. Universal coalgebra: A theory of systems. Theoretical Computer Science, 249(1):3-80, 2000.
19. P. Jansson, J. Jeuring. Polytypic compact printing and parsing. Programming Languages and Systems, pages 639-639, 1999.
20. Luca Aceto, Jan Friso Groote. A complete equational axiomatization for MPA with string iteration. Theoretical Computer Science, 211(1):339-374, 1999.
21. B. Jacobs, J. Rutten. A tutorial on (co) algebras and (co) induction. EATCS Bulletin, 62(222):3-7, 1997.
22. Nicholas Pippenger. Regular Languages and Stone Duality. Theory Comput. Syst, 30(2):121-134, 1997.
23. Dexter Kozen. Kleene Algebra with Tests. Transactions on Programming Languages and Systems, 19(3):427-443, May 1997.
24. Luca Aceto, Alan Jeffrey. A complete axiomatization of timed bisimulation for a class of timed regular behaviours. Theoretical Computer Science, 152(2):251-268, 1995.
25. S\oren Christensen, Hans H\"uttel, Colin Stirling. Bisimulation Equivalence is Decidable for All Context-Free Processes. Information and Computation, 121(2):143-148, September 1995.
26. Jan Friso Groote, Hans Hüttel. Undecidable Equivalences for Basic Process Algebra. Information and Computation, 115(2):354-371, December 1994.
27. Thomas Wilke. Alternating Tree Automata, Parity Games, and Modal μ-Calculus. Bull. Belg. Math. Soc, 0:359-391, 1993.
28. D. Kozen. On the Myhill-Nerode Theorem for Trees. Bulletin of the European Assocation for Theoretical Computer Science (EATCS Bull.), 47:170-173, June 1992.
29. Robin Milner. A Complete Axiomatisation for Observational Congruence of Finite-State Behaviors. Information and Computation, 81(2):227-247, May 1989.
30. B. Courcelle. Equivalences and Transformations of Regular Systems - Applications to Recursive Program Schemes and Grammars. Theoretical Computer Science, 42:1-122, 1986.
31. Robin Milner. A Complete Inference System for a Class of Regular Behaviours. Journal of Computer and System Sciences (JCSS), 28:439-466, 1984.
32. Bruno Courcelle. Fundamental properties of infinite trees. Theoretical Computer Science, 25(2):95-169, 1983.
33. J. Goguen, J. Thatcher, E. Wagner, J. Wright. Initial Algebra Semantics and Continuous Algebras. J. of the ACM, 24(1):68-95, January 1977.
34. Jay Earley. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94-102, 1970. download
35. J.E. Hopcroft. On the equivalence and containment problems for context-free languages. Theory of Computing Systems, 3(2):119-124, 1969.
36. Noam Chomsky. On certain formal properties of grammars. Information and Control, 2(2):137-167, 1959.
37. N. Chomsky. Three models for the description of language. Information Theory, IEEE Transactions on, 2(3):113-124, 1956.

Book Chapters

1. Oscar Nierstrasz. Regular Types for Active Objects. In Object-Oriented Software Composition, O. Nierstrasz, D. Tsichritzis (eds.), pp. 99-121, Prentice Hall, 1995.
2. D. Kozen. On action algebras. In Logic and Information Flow, Jan van Eijck, Albert Visser (eds.), Chap. 5, pp. 78-88, Foundations of Computing, MIT Press, 1994.
3. Jean Berstel, Luc Boasson. Context-Free Languages. In Handbook of Theoretical Computer Science, Vol. Formal Models and Sematics (B), Chap. 2, pp. 59-102, Elsevier, 1990.
4. Arto Salomaa. Formal Languages and Power Series. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 103-132, 1990.
5. J. Thatcher. Tree Automata: An Informal Survey. In Currents in the Theory of Computing, A. Aho (ed.), pp. 143-172, Prentice-Hall, 1973.

International Conferences

1. K. Mizushima, A. Maeda, Y. Yamaguchi. Packrat Parsers Can Handle Practical Grammars in Mostly Constant Space. In PASTE, 2010.
2. Giorgios Economopoulos, Paul Klint, Jurgen J. Vinju. Faster Scannerless GLR Parsing. In Proc. International Conference on Compiler Construction, Pages 126-141, 2009.
3. Grigore Rosu, Dorel Lucanu. Circular coinduction: A proof theoretical foundation. In Proc. 3rd Conference on Algebra and Coalgebra in Computer Science (CALCO), Lecture Notes in Computer Science (LNCS), ISBN 978-3-642-03740-5, Pages 127-144, September 2009.
4. J. Worthington. Automatic proof generation in Kleene algebra. In Proceedings of the 10th international conference on Relational and kleene algebra methods in computer science, and 5th international conference on Applications of kleene algebra, Lecture Notes in Computer Science (LNCS), Volume 4988, Pages 382-396, 2008.
5. Dexter Kozen, Wei-Lung Dustin Tseng. The Böhm-Jacopini Theorem Is False, Propositionally. In MPC, Pages 177-192, 2008.
6. Ralf Hinze. Functional pearl: streams and unique fixed points. In ICFP '08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, Pages 189-200, New York, NY, USA, 2008. download
7. Sylvain Schmitz. Conservative Ambiguity Detection in Context-Free Grammars. In Proc. 34th International Colloquium on Automata, Languages and Programming, ICALP\ '07, 2007.
8. Martin Sulzmann, Kenny Zhuo Ming Lu. XHaskell - Adding Regular Expression Types to Haskell. In Proc. Workshop on Implementation and Application of Functional Languages (IFL), Pages 75-92, 2007.
9. Jérôme Vouillon. Polymorphic regular tree types and patterns. In POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Pages 103-114, New York, NY, USA, 2006. download
10. Haruo Hosoya, Alain Frisch, Giuseppe Castagna. Parametric polymorphism for XML. In POPL, Pages 50-62, 2005. download
11. Alain Frisch. Regular Tree Language Recognition with Static Information. In IFIP TCS, Pages 661-674, 2004.
12. Bryan Ford. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. In Symposium on Principles of Programming Languages\ (POPL'04), Pages 111-122, 2004.
13. Vladimir Gapeyev, Benjamin C. Pierce. Regular Object Types. In ECOOP, Pages 151-175, 2003.
14. Alain Frisch, Giuseppe Castagna, Véronique Benzaken. Semantic Subtyping. In LICS, Pages 137-146, 2002.
15. M. G. J. van den Brand, J. Scheerder, J. J. Vinju, E. Visser. Disambiguation Filters for Scannerless Generalized LR Parsers. In Proc. Compiler Construction 2002, 2002.
16. B. Ford. Packrat Parsing: Simple, Powerful, Lazy, Linear Time (Functional Pearl). In Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming (ICFP), Pages 36-47, 2002.
17. Zolt\'an Ésik, Hans Lei\ss. Greibach Normal Form in Algebraically Complete Semirings. In CSL '02: Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, Pages 135-150, London, UK, 2002.
18. Y. Liu, N. Li, S. Stoller. Solving regular tree grammar based constraints. In Proc. Static Analysis Symposium (SAS), Pages 213-233, 2001.
19. Quanzhong Li, Bongki Moon. Indexing and Querying XML Data for Regular Path Expressions. In VLDB, Pages 361-370, 2001.
20. Haruo Hosoya, Jerome Vouillon, Benjamin C. Pierce. Regular expression types for XML. In ICFP, Pages 11-22, 2000. download
21. Jan J. M. M. Rutten. Automata and Coinduction (An Exercise in Coalgebra). In CONCUR, Pages 194-218, 1998.
22. D. Kozen, F. Smith. Kleene algebra with tests: Completeness and decidability. In Computer Science Logic, Pages 244-259, 1997.
23. A. Aiken, D. Kozen, M. Vardi, E. Wimmers. The complexity of set constraints. In Computer Science Logic, Pages 1-17, 1994.
24. R. De Nicola, A. Labella. A completeness theorem for nondeterministic Kleene algebras. In Mathematical Foundations of Computer Science 1994, Pages 536-545, 1994.
25. Moshe Y. Vardi. Nontraditional Applications of Automata Theory. In Proc. Int'l Symp. on Theoretical Aspects of Computer Software (TACS), Masami Hagiya, John C. Mitchell (eds.), Lecture Notes in Computer Science (LNCS), Volume 789, Pages 575-597, Sendai, Japan, April 1994.
26. Hans Lei\ss. Towards Kleene Algebra with Recursion. In CSL '91: Proceedings of the 5th Workshop on Computer Science Logic, Pages 242-256, London, UK, 1992.
27. D. Kozen. On Kleene algebras and closed semirings. In Mathematical Foundations of Computer Science 1990, Pages 26-47, 1990.
28. Vaughan Pratt. Action Logic and Pure Induction. In Proc. Logics in AI: European Workshop JELIA, Lecture Notes in Computer Science (LNCS), Volume 478, Pages 97-120, 1990.
29. H. Seidl. Deciding Equivalence of Finite Tree Automata. In Proc. 6th Annual Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science (LNCS), Volume 349, Pages 480-492, February 1989.
30. A. Colmerauer. Equations and Inequations on Finite and Infinite Trees. In Proc. Int'l Conf. on Fifth Generation Computer Systems, 1984.
31. David Park. Concurrency and Automata on Infinite Sequences. In Proc.\ 5th GI-Conf.\ Theoretical Computer Science, Karlsruhe, Germany, Lecture Notes in Computer Science (LNCS), Volume 104, Pages 167-183, March 1981.
32. Marvin Solomon. Type definitions with parameters. In POPL '78: Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, Pages 31-38, New York, NY, USA, January 1978. download

Technical Reports

1. Dexter Kozen. On the Coalgebraic Theory of Kleene Algebra with Tests. Research Report Computing and Information Science, Cornell University, March 2008.
2. H. Lei\ss. $\mu$-Regular Algebra. Research Report Centrum für Informations- und Sprachverarbeitung, Ludwigs-Maximilians-Universität München, No 91, 1991.
3. Michael J. Maher. Complete Axiomatizations of the Algebras of Finite, Rational and Infinite Trees. Research Report IBM T.J.\ Watson Research Center, Yorktown Heights, New York, 1988.
4. P. Bloniarz, H. Hunt, D. Rosenkrantz. Algebraic Structures with Hard Equivalence and Minimization Problems. Research Report SUNY, No 82, March 1982.

Dissertations

1. Alain Frisch. Théorie, conception et réalisation d'un langage de programmation adapté à XML. PhD Thesis University of Paris 7, 2004.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.