Graduate studies at Western
Journal of Symbolic Logic 39 (3):489-495 (1974)
|Abstract||In this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability D, the existence of an RPCF whose word problem is of degree D and an RPCF with axiom whose decision problem is also of degree D. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
M. Gehrke & H. A. Priestley (2007). Duality for Double Quasioperator Algebras Via Their Canonical Extensions. Studia Logica 86 (1):31 - 68.
Christopher Steinsvold (2010). A Canonical Topological Model for Extensions of K. Studia Logica 94 (3):433 - 441.
Charles E. Hughes (1976). Two Variable Implicational Calculi of Prescribed Many-One Degrees of Unsolvability. Journal of Symbolic Logic 41 (1):39-44.
Maria Lasonen-Aarnio (2008). Single Premise Deduction and Risk. Philosophical Studies 141 (2):157 - 173.
Nguyen Cat Ho & Helena Rasiowa (1987). Semi-Post Algebras. Studia Logica 46 (2):149 - 160.
Charles E. Hughes & David W. Straight (1980). Word Problems for Bidirectional, Single-Premise Post Systems. Notre Dame Journal of Formal Logic 21 (3):501-508.
Timothy J. Surendonk (2001). Canonicity for Intensional Logics with Even Axioms. Journal of Symbolic Logic 66 (3):1141-1156.
Added to index2009-01-28
Total downloads2 ( #246,325 of 739,318 )
Recent downloads (6 months)0
How can I increase my downloads?