Design and simulation of two-way quantum finite automata
| dc.contributor | Graduate Program in Computer Engineering. | |
| dc.contributor.advisor | Say, Ahmet Celal Cem. | |
| dc.contributor.author | Atak, Fatih Mehmet. | |
| dc.date.accessioned | 2023-03-16T10:06:13Z | |
| dc.date.available | 2023-03-16T10:06:13Z | |
| dc.date.issued | 2006. | |
| dc.description.abstract | In this thesis, we review classical finite state automata, (FSAs and TWAs) and 2- way quantum finite state automata (2QFAs). We examine fundamental theorems and their proofs. We develop a software simulator of quantum finite state automata. We introduce the simulator and by the help of the simulator, we examine some non-regular languages like {0n1n n > 0} (type 2) and {0n1n2n n > 0} (type 1). We also propose a new technique to enhance the language recognition probability of 2QFAs. This method may allow some languages to be recognized with bounded error, if we have an algorithm for the unbounded error version. A sample construction for such a case is inspected in detail. Using this technique, we enhance the complexity of a 2QFA which originally recognize string s with error probability of 1/2, beyond a well known 2QFA in the literature for the same language. | |
| dc.format.extent | 30cm. | |
| dc.format.pages | xii, 170 leaves; | |
| dc.identifier.other | CMPE 2006 A82 | |
| dc.identifier.uri | https://digitalarchive.library.bogazici.edu.tr/handle/123456789/12499 | |
| dc.publisher | Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2006. | |
| dc.relation | Includes appendices. | |
| dc.relation | Includes appendices. | |
| dc.subject.lcsh | Machine theory. | |
| dc.title | Design and simulation of two-way quantum finite automata |