Automata theory based on quantum logic II

被引:75
作者
Ying, MS [1 ]
机构
[1] Dept Comp Sci, State Key Lab Intelligent Technol & Systems, Beijing 100084, Peoples R China
[2] Tsinghua Univ, Beijing 100084, Peoples R China
关键词
Field Theory; Elementary Particle; Quantum Field Theory; Quantum Logic; Automaton Theory;
D O I
10.1023/A:1026453524064
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We establish the pumping lemma in automata theory based on quantum logic under certain conditions on implication, and discuss the recognizability by the product and union of orthomodular lattice-valued (quantum) automata. In particular, we show that the equivalence between the recognizabilty by the product of automata and the conjunction of the recognizabilities by the factor automata is equivalent to the distributivity of meet over union in the truth-value set.
引用
收藏
页码:2545 / 2557
页数:13
相关论文
共 17 条
[1]   The logic of quantum mechanics [J].
Birkhoff, G ;
von Neumann, J .
ANNALS OF MATHEMATICS, 1936, 37 :823-843
[2]  
DALLACHIARA ML, 1986, HDB PHILOS LOGIC, V3, P427
[3]   QUANTUM-THEORY, THE CHURCH-TURING PRINCIPLE AND THE UNIVERSAL QUANTUM COMPUTER [J].
DEUTSCH, D .
PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1985, 400 (1818) :97-117
[4]  
Eilenberg S., 1974, AUTOMATA LANGUAGES M, VA
[5]   SIMULATING PHYSICS WITH COMPUTERS [J].
FEYNMAN, RP .
INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 1982, 21 (6-7) :467-488
[6]   QUANTUM-MECHANICAL COMPUTERS [J].
FEYNMAN, RP .
FOUNDATIONS OF PHYSICS, 1986, 16 (06) :507-531
[7]  
Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation
[8]  
MOORE C, IN PRESS THEOR COMPU
[9]   QUANTUM LOGIC REVISITED [J].
ROMAN, L ;
RUMBOS, B .
FOUNDATIONS OF PHYSICS, 1991, 21 (06) :727-734
[10]   Quantum implication [J].
Román, L ;
Zuazua, RE .
INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 1999, 38 (03) :793-797