# CJam, <s>72</s> <s>68</s> 59 bytes

 q_'.e=\N/{)'?=\S/>_,(%}%/(_,m*{{1$1$1>#2$@+3%@?}*}%ff{\e=N}

This works well for the first test case in practice, but it's way too slow and memory hungry for the second one. Try it online in the [CJam interpreter][1].

[1]: http://cjam.aditsu.net/#code=q_'.e%3D%5CN%2F%7B)'%3F%3D%5CS%2F%3E_%2C(%25%7D%25%2F(_%2Cm*%7B%7B1%241%241%3E%232%24%40%2B3%25%40%3F%7D*%7D%25ff%7B%5Ce%3DN%7D&input=B%20is%20a%20A.%0AC%20is%20a%20B.%0AA%20has%20a%20foo.%0ADoes%20B%20have%20a%20foo%3F%0AIs%20C%20a%20A%3F%0AIs%20D%20a%20A%3F

---

# CJam, <s>76</s> <s>72</s> 63 bytes

 q_'.e=\N/{)'?=\S/>_,(%}%/(_,{__f{{1$1>#!},\f{\+3%}~}|}*ff{\e=N}

This finishes instantly for both test cases. Try it online in the [CJam interpreter][2].

[2]: http://cjam.aditsu.net/#code=q_'.e%3D%5CN%2F%7B)'%3F%3D%5CS%2F%3E_%2C(%25%7D%25%2F(_%2C%7B__f%7B%7B1%241%3E%23!%7D%2C%5Cf%7B%5C%2B3%25%7D~%7D%7C%7D*ff%7B%5Ce%3DN%7D&input=Cop%20is%20a%20Person.%0ACriminal%20is%20a%20Person.%0ASheriff%20is%20a%20Cop.%0ACrooked_Cop%20is%20a%20Cop.%0ACrooked_Cop%20is%20a%20Criminal.%0ABankRobber%20is%20a%20Criminal.%0ACop%20has%20a%20badge.%0ACriminal%20has%20a%20criminal_record.%0APerson%20has%20a%20name.%0AIs%20Crooked_Cop%20a%20Person%3F%0ADoes%20Criminal%20have%20a%20name%3F%0AIs%20Crooked_Cop%20a%20BankRobber%3F%0ADoes%20Person%20have%20a%20potato%3F