On the class of languages recognizable by 1-way quantum finite automata

Andris Ambainis; Arnolds Kikusts; Maris Valdats

REVIEW

On the class of languages recognizable by 1-way quantum finite automata

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv quant-ph/0009004 v1 pith:DMFNDRCN submitted 2000-09-01 quant-ph

Andris Ambainis , Arnolds Kikusts , Maris Valdats This is my paper

classification quant-ph

keywords languagesclassrecognizableautomatafinitenecessaryquantumregular

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.

Discussion (0). Sign in to comment.

Pith tools