Reflection in the Chomsky Hierarchy

Barendregt, Henk; Capretta, Venanzio; Kozen, Dexter

Reflection in the Chomsky Hierarchy

File(s)

reflexive_languages.pdf (231.36 KB)

Main article

Permanent Link(s)

https://hdl.handle.net/1813/29612

Collections

Computing and Information Science Technical Reports

Author

Barendregt, Henk

Capretta, Venanzio

Kozen, Dexter

Abstract

We investigate which classes of formal languages in the Chomsky hierarchy are reflexive, that is, contain a language of codes that is universal for the whole class.

Date Issued

2012-07-31

Keywords

reflection

•

Chomsky hierarchy

Related Version

Corrected version of: H. Barendregt and V. Capretta, Reflection in the Chomsky Hierarchy. In: Liber Amicorum for Roel de Vrijer, Eds. Klop, van Oostrom and van Raamsdonk. pp. 13-20. 2009.

Type

technical report