Jumps of nontrivial splittings of recursively enumerable sets | Zendy

Ingrassia Michael A. | Zendy; Lempp Steffen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Jumps of nontrivial splittings of recursively enumerable sets

Author(s) -

Ingrassia Michael A.,

Lempp Steffen

Publication year - 1990

Publication title -

mathematical logic quarterly

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.473

H-Index - 28

eISSN - 1521-3870

pISSN - 0942-5616

DOI - 10.1002/malq.19900360403

Subject(s) - recursively enumerable language , citation , state (computer science) , mathematics , computer science , algorithm , discrete mathematics , library science , combinatorics

A pair of recursively enumerable (r.e.) sets A. and A l is said to split an r.e. set A if A = A. u A, (i.e., A = A. u Al and 0 = A. n Al). FRIEDBERG [5] was the first to prove that any nonrecursive r.e. set can be split into two nonrecursive r.e. sets. SACKS [15] improved this result by showing that the two halves can be made of low incomparable degrees. Other wellknown splitting results were obtained by OWINGS [13], R. W. ROBINSON [14], MORLEY and SOARE [12], and LACHLAN [8].

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research