Towards a Coalgebraic Chomsky Hierarchy

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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.265-280, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_21〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402071
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 11:05:37
Dernière modification le : mercredi 18 octobre 2017 - 20:08:04
Document(s) archivé(s) le : mardi 21 mars 2017 - 07:07:09

Fichier

978-3-662-44602-7_21_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Sergey Goncharov, Stefan Milius, Alexandra Silva. Towards a Coalgebraic Chomsky Hierarchy. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.265-280, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_21〉. 〈hal-01402071〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

9