Index sets for ω‐languages

Mathematical Logic Quarterly 49 (1):22-33 (2003)
  Copy   BIBTEX


An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language



    Upload a copy of this work     Papers currently archived: 84,213

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Index sets and parametric reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
Kleene index sets and functional m-degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Global index grammars and descriptive power.José M. Castaño - 2004 - Journal of Logic, Language and Information 13 (4):403-419.
Index sets for Π01 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
Lusin-sierpinski index for the internal sets.Boško Živaljević - 1992 - Journal of Symbolic Logic 57 (1):172 - 178.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.


Added to PP

19 (#622,865)

6 months
2 (#331,692)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Index sets for computable differential equations.Douglas Cenzer & Jeffrey B. Remmel - 2004 - Mathematical Logic Quarterly 50 (4-5):329-344.

Add more citations

References found in this work

No references found.

Add more references