Automata and Grammars Theory Based on Quantum Logic
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [15]
  • |
  • Related [20]
  • |
  • Cited by [10]
  • | |
  • Comments
    Abstract:

    In this paper, a fundamental framework of automata and grammars theory based on quantum logic is preliminarily established. First, the introduce quantum grammar, which is called l valued grammars, is introduced. It is particularly showed that the language (called quantum language) generated by any l valued regular grammar is equivalent to that recognized by some automaton with e moves based on quantum logic (called l valued automata), and conversely, any quantum language recognized by l valued automaton is also equivalent to that generated by some l valued grammar. Afterwards, the l valued pumping lemma is built, and then a decision characterization of quantum languages is presented. Finally, the relationship between regular grammars and quantum grammars (l valued regular grammars) is briefly discussed. Summarily, the introduced work lays a foundation for further studies on more complicated quantum automata and quantum grammars such as quantum pushdown automata and Turing machine as well as quantum context-free grammars and context-sensitive grammars.

    Reference
    [1]Benioff P. The computer as a physical system: a microsopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Physical Review Letters, 1982,48(23):1581~1585.
    [2]Feynman RP. Simulating physics with computers. International Journal of Theoretical Physics, 1986,21(6-7):467~488.
    [3]Feynman RP. Quantum mechanical computers. Foundation of Physics, 1986,16(6):507~531.
    [4]Deutsh D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 1985,400(1818):97~117.
    [5]Shor PW. Polynomial-Time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997,26(5):1484~1509.
    [6]Grover L. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 1997,79(2):326~328.
    [7]Lloyd S. A potentially realizable quantum computer. Science, 1993,261(5128):1569~1571.
    [8]Cirac JI, Zoller P. Quantum computations with cold trapped ions. Physical Review Letters, 1995,74(20):4091~4094.
    [9]Moore C, Crutchfield JP. Quantum automata and quantum grammars. Theoretical Computer Science, 2000,237(1-2):275~306.
    [10]Gudder S. Basic Properties of Quantum Automata. Foundation of Physics, 2000,30(2):301~319.
    [11]Birkhoff G, von Neumann J. The logic of quantum mechanics. Annals of Mathematics, 1936,37(4):823~843.
    [12]Pták P, Pulmannová S. Orthomodular Structures as Quantum Logics. Dordrecht: Kluwer Academic Publishers, 1991.
    [13]Ying MS. Automata theory based on quantum logic (I). International Journal of Theoretical Physics, 2000,39(4):891~991.
    [14]Ying MS. Automata theory based on quantum logic (II). International Journal of Theoretical Physics, 2000,39(11):2545~2557.
    [15]Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. New York: Addison-Wesly, 1979. 13~223.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

邱道文.基于量子逻辑的自动机和文法理论.软件学报,2003,14(1):23-27

Copy
Share
Article Metrics
  • Abstract:4181
  • PDF: 5253
  • HTML: 0
  • Cited by: 0
History
  • Received:March 29,2001
  • Revised:May 18,2001
You are the first2032795Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063