𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Index sets for ω-languages

✍ Scribed by Douglas Czenzer; Jeffrey B. Remmel

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
223 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An ω‐language is a set of infinite sequences (words) 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 $ \Sigma ^0 _2 $ languages, may enumerated as P~0~, P~1~, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that P~e~ 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.

📜 SIMILAR VOLUMES

Extending ω-consistent sets to maximally
Extending ω-consistent sets to maximally consistent, ω-complete sets
✍ George Weaver; Michael Thau; Hugues Leblanc 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

EXTENDING w-CONSISTENT SETS TO MAXIMALLY CONSISTENT, IN-COMPLETE SETS by GEORGE WEAVER in Bryn Mawr, Pennsylvania MICHAEL THAU and HUGUES LEBLANC in Philadelphia, Pennsylvania (U.S.A.) ') Given L, a first order language, HENKIN'S completeness proof for L proceeds by showing that every consistent se

Index sets for computable differential e
Index sets for computable differential equations
✍ Douglas Cenzer; Jeffrey B. Remmel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB

## Abstract Index sets are used to measure the complexity of properties associated with the differentiability of real functions and the existence of solutions to certain classic differential equations. The new notion of a locally computable real function is introduced and provides several examples

ω-operations over partial enumerated set
ω-operations over partial enumerated sets
✍ Andrzej Orlicki 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 445 KB

## Abstract In the present paper we concentrate on fundamental problems concerning ω‐operations over partial enumerated sets. The notion of “HOM‐lifts” seems to be an adequate tool for this kind of investigations. MSC: 03D45, 18A30.

Languages for automation
Languages for automation
✍ Zvieli, Arie 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 829 KB