9
$\begingroup$

IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic finite automata with a two-way input head.

Are any closure properties of these classes known?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You can take a look at the following paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers I: the power of interaction. J. ACM 39, 4 (Oct. 1992), 800-828. DOI= http://doi.acm.org/10.1145/146585.146599

or the related paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers II: zero knowledge. J. ACM 39, 4 (Oct. 1992), 829-858. DOI= http://doi.acm.org/10.1145/146585.146601

Improve this answer
$\endgroup$
2
  • $\begingroup$ I've already gone through those papers and others by Condon, Lipton et al., but there's nothing there about the closure properties of these classes. $\endgroup$
    – Cem Say
    Sep 23, 2010 at 10:25
  • 1
    $\begingroup$ @Cem: Can you clarify on the definition of "closure"? In particular, under what kind of operation do you seek closure? $\endgroup$
    – Sadeq Dousti
    Sep 23, 2010 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.