Abstract
The Chomsky hierarchy plays a prominent role in the foundations of theoretical computer science relating classes of formal languages of primary importance. In this paper we use recent developments on coalgebraic and monad-based semantics to obtain a generic notion of a \(\mathbb{T}\)-automaton, where \(\mathbb{T}\) is a monad, which allows the uniform study of various notions of machines (e.g. finite state machines, multi-stack machines, Turing machines, weighted automata). We use the generalized powerset construction to define a generic (trace) semantics for \(\mathbb{T}\)-automata, and we show by numerous examples that it correctly instantiates for some known classes of machines/languages captured by the Chomsky hierarchy. Moreover, our approach provides new generic techniques for studying expressivity power of various machine-based models.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Haskell 98 Language and Libraries — The Revised Report. Cambridge University Press (2003); also: J. Funct. Prog. 13 (2003)
Adámek, J., Milius, S., Velebil, J.: Iterative algebras at work. Math. Structures Comput. Sci. 16(6), 1085–1131 (2006)
Bonsangue, M.M., Milius, S., Silva, A.: Sound and complete axiomatizations of coalgebraic language equivalence. ACM Trans. Comput. Log. 14(1), 7:1–7:52 (2013)
Book, R.V., Greibach, S.A.: Quasi-realtime languages. Mathematical Systems Theory 4(2), 97–111 (1970)
Brzozowski, J.A.: Derivatives of regular expressions. J. ACM 11(4), 481–494 (1964)
Coumans, D., Jacobs, B.: Scalars, monads, and categories. In: Sadrzadeh, C.H.M., Grefenstette, E. (eds.) Quantum physics and linguistics. A compositional, diagrammatic discourse, pp. 184–216. Oxford University Press (2013)
Courcelle, B.: Fundamental properties of infinite trees. Theoretical Computer Science 25(2), 95–169 (1983)
Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. Springer (2009)
Eilenberg, S.: Automata, Languages, and Machines. Pure and Applied Mathematics, vol. A. Academic Press (1974)
Fiore, M.P., Moggi, E., Sangiorgi, D.: A fully abstract model for the π-calculus. Inf. Comput. 179(1), 76–117 (2002)
Freyd, P.: Algebra valued functors in general and tensor products in particular. Colloq. Math. 14, 89–106 (1966)
Goguen, J.A., Thatcher, J.W., Wagner, E.G., Wright, J.B.: Initial algebra semantics and continuous algebras. J. ACM 24(1), 68–95 (1977)
Goncharov, S.: Trace semantics via generic observations. In: Heckel, R., Milius, S. (eds.) CALCO 2013. LNCS, vol. 8089, pp. 158–174. Springer, Heidelberg (2013)
Hyland, M., Levy, P.B., Plotkin, G.D., Power, J.: Combining algebraic effects with continuations. Theor. Comput. Sci. 375(1-3), 20–40 (2007)
Jacobs, B.: A bialgebraic review of deterministic automata, regular expressions and languages. In: Futatsugi, K., Jouannaud, J.-P., Meseguer, J. (eds.) Algebra, Meaning, and Computation. LNCS, vol. 4060, pp. 375–404. Springer, Heidelberg (2006)
Jacobs, B.: Coalgebraic trace semantics for combined possibilitistic and probabilistic systems. Electr. Notes Theor. Comput. Sci. 203(5), 131–152 (2008)
Jacobs, B., Silva, A., Sokolova, A.: Trace semantics via determinization. In: Pattinson, D., Schröder, L. (eds.) CMCS 2012. LNCS, vol. 7399, pp. 109–129. Springer, Heidelberg (2012)
Kock, A.: On double dualization monads. Math. Scand. 27, 151–165 (1970)
Lane, S.M.: Categories for the Working Mathematician. Springer (1971)
Milius, S.: A sound and complete calculus for finite stream circuits. In: Proc. 25th Annual Symposium on Logic in Computer Science (LICS 2010), pp. 449–458. IEEE Computer Society (2010)
Moggi, E.: Notions of computation and monads. Inf. Comput. 93, 55–92 (1991)
Myers, R.: Rational Coalgebraic Machines in Varieties: Languages, Completeness and Automatic Proofs. Ph.D. thesis, Imperial College London (2013)
Plotkin, G., Power, J.: Notions of computation determine monads. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol. 2303, pp. 342–356. Springer, Heidelberg (2002)
Power, J., Shkaravska, O.: From comodels to coalgebras: State and arrays. In: CMCS 2004. ENTCS, vol. 106, pp. 297–314 (2004)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114–125 (1959)
Rutten, J.: Universal coalgebra: A theory of systems. Theor. Comput. Sci. 249, 3–80 (2000)
Rutten, J.J.M.M.: Behavioural differential equations: A coinductive calculus of streams, automata, and power series. Theor. Comput. Sci. 308(1-3), 1–53 (2003)
Segala, R.: Modelling and Verification of Randomized Distributed Real-Time Systems. Ph.D. thesis, Massachusetts Institute of Technology (1995)
Segala, R., Lynch, N.A.: Probabilistic simulations for probabilistic processes. Nordic Journal of Computing 2(2), 250–273 (1995)
Silva, A.: Kleene coalgebra. Ph.D. thesis, Radboud Univ. Nijmegen (2010)
Silva, A., Bonchi, F., Bonsangue, M., Rutten, J.: Generalizing determinization from automata to coalgebras. LMCS 9(1) (2013)
Syme, D., Granicz, A., Cisternino, A.: Expert F#. Apress (2007)
Varacca, D., Winskel, G.: Distributing probability over non-determinism. Math. Struct. Comput. Sci. 16, 87–113 (2006)
Winter, J., Bonsangue, M.M., Rutten, J.J.M.M.: Coalgebraic characterizations of context-free languages. LMCS 9(3) (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Goncharov, S., Milius, S., Silva, A. (2014). Towards a Coalgebraic Chomsky Hierarchy. In: Diaz, J., Lanese, I., Sangiorgi, D. (eds) Theoretical Computer Science. TCS 2014. Lecture Notes in Computer Science, vol 8705. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44602-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-662-44602-7_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44601-0
Online ISBN: 978-3-662-44602-7
eBook Packages: Computer ScienceComputer Science (R0)