1. Daniel E. Cohen, Klaus Madlener & Friedrich Otto (1993). Seperating the Intrinsic Complexity and the Derivational Complexity of the Word Problem for Finitely Presented Groups. Mathematical Logic Quarterly 39 (1):143-157.
    A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Daniel E. Cohen (1987). Computability and Logic. Halsted Press.
     
    My bibliography  
     
    Export citation  
  3. Daniel E. Cohen (1980). Degree Problems for Modular Machines. Journal of Symbolic Logic 45 (3):510-528.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation