Index sets for ω‐languages

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

Abstract

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

Categories

Keywords

Reprint years

DOI

10.1002/malq.200310002

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

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

Through your library

My notes

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.
A Note on the Computation of the Mean Random Consistency Index of the Analytic Hierarchy Process (Ahp).V. M. Rao Tummala & Hong Ling - 1998 - Theory and Decision 44 (3):221-230.
Index sets for Π01 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.
Review: Louise Hay, On Creative Sets and Indices of Partial Recursive Functions; Louise Hay, Isomorphism Types of Index Sets of Partial Recursive Functions; Louise Hay, Index Sets of Finite Classes of Recursively Enumerable Sets. [REVIEW]Forbes D. Lewis - 1974 - Journal of Symbolic Logic 39 (1):186-187.
Lusin-sierpinski index for the internal sets.Boško Živaljević - 1992 - Journal of Symbolic Logic 57 (1):172 - 178.
A note on the choice of appropriate index of inflation for india.Mita H. Suthar - unknown
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Boolean Algebras, Tarski Invariants, and Index Sets.Barbara F. Csima, Antonio Montalbán & Richard A. Shore - 2006 - Notre Dame Journal of Formal Logic 47 (1):1-23.

Analytics

Added to PP
2013-12-01

Downloads
21 (#715,461)

6 months
3 (#1,023,809)

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

Recursive constructions in topological spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
$\pi^0_1$-classes And Rado's Selection Principle.C. G. Jockusch, A. Lewis & J. B. Remmel - 1991 - Journal of Symbolic Logic 56 (2):684-693.
Index sets for Π01 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
Π01-classes and Rado's selection principle.C. G. Jockusch, A. Lewis & J. B. Remmel - 1991 - Journal of Symbolic Logic 56 (2):684 - 693.

Add more references