Open AccessThe ‘almost all’ theory of subrecursive degrees is decidable
Author(s) -
Kurt Mehlhorn
Publication year - 1974
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-06841-4
DOI - 10.1007/3-540-06841-4_70
Subject(s) - decidability , quantifier (linguistics) , constructive , relation (database) , computer science , constant (computer programming) , quantifier elimination , measure (data warehouse) , discrete mathematics , mathematics , algebra over a field , algorithm , pure mathematics , artificial intelligence , programming language , data mining , process (computing)
We use constructive measure theory to show the decidability of the almost all theory of subrecursive degrees. The formulas of this theory are built up using the constant 0 standing for the minimum degree, the functions , standing for the join and meet of two degrees respectively, the relation standing for the reducibility the logical connectives &, , and the quantifier (for almost all a). An efficient decision procedure is described.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom