mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Quantum finite multitape automata
University of California, Berkeley, USA.
Mälardalen University, Department of Mathematics and Physics.
University of Latvia, Latvia.
University of Latvia, Latvia.
Show others and affiliations
1999 (English)In: SOFSEM’99: Theory and Practice of Informatics: 26th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 27 — December 4, 1999 Proceedings, 1999, Vol. 1725, p. 340-348Conference paper, Published paper (Refereed)
Abstract [en]

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved Chat for some languages quantum finite automats may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multi-tape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automats. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.

Place, publisher, year, edition, pages
1999. Vol. 1725, p. 340-348
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1725
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:mdh:diva-2980DOI: 10.1007/3-540-47849-3_21ISI: 000088669000021Scopus ID: 2-s2.0-84957016687ISBN: 978-3-540-66694-3 (print)OAI: oai:DiVA.org:mdh-2980DiVA, id: diva2:115644
Conference
26th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 27 — December 4, 1999
Available from: 2008-03-08 Created: 2008-03-08 Last updated: 2016-05-17Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Bonner, R.
By organisation
Department of Mathematics and Physics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 73 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf