# CJam, 72 bytes

 qN/_{'.&},_{W<S/_,(%}%_,m*{{1$1$1>#{+3%}{;}?}*}%@@-{W<S/1>_,(%}%\f{\e=N}

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

[1]: http://cjam.aditsu.net/#code=qN%2F_%7B'.%26%7D%2C_%7BW%3CS%2F_%2C(%25%7D%25_%2Cm*%7B%7B1%241%241%3E%23%7B%2B3%25%7D%7B%3B%7D%3F%7D*%7D%25%40%40-%7BW%3CS%2F1%3E_%2C(%25%7D%25%5Cf%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, 76 bytes

 qN/_{'.&},_{W<S/_,(%}%_,{__f{{1$1>#!},\0=f{0\t}~}|}*@@-{W<S/1>_,(%}%\f{\e=N}

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

[2]: http://cjam.aditsu.net/#code=qN%2F_%7B'.%26%7D%2C_%7BW%3CS%2F_%2C(%25%7D%25_%2C%7B__f%7B%7B1%241%3E%23!%7D%2C%5C0%3Df%7B0%5Ct%7D~%7D%7C%7D*%40%40-%7BW%3CS%2F1%3E_%2C(%25%7D%25%5Cf%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