Quantum finite automata with control language

Carlo Mereghetti; Beatrice Palano

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 2, page 315-332
  • ISSN: 0988-3754

Abstract

top
Bertoni et al.  introduced in Lect. Notes Comput. Sci.2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.

How to cite

top

Mereghetti, Carlo, and Palano, Beatrice. "Quantum finite automata with control language." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 315-332. <http://eudml.org/doc/249736>.

@article{Mereghetti2006,
abstract = { Bertoni et al.  introduced in Lect. Notes Comput. Sci.2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata. },
author = {Mereghetti, Carlo, Palano, Beatrice},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Quantum computing; quantum finite automata.; quantum computing; quantum finite automata},
language = {eng},
month = {7},
number = {2},
pages = {315-332},
publisher = {EDP Sciences},
title = {Quantum finite automata with control language},
url = {http://eudml.org/doc/249736},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Mereghetti, Carlo
AU - Palano, Beatrice
TI - Quantum finite automata with control language
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/7//
PB - EDP Sciences
VL - 40
IS - 2
SP - 315
EP - 332
AB - Bertoni et al.  introduced in Lect. Notes Comput. Sci.2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.
LA - eng
KW - Quantum computing; quantum finite automata.; quantum computing; quantum finite automata
UR - http://eudml.org/doc/249736
ER -

References

top
  1. A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer and D. Thérien, Algebraic Results on Quantum Automata. Theory Comput. Syst.39 (2006) 165–188.  
  2. A. Ambainis and R. Freivalds, 1-way Quantum Finite Automata: Strengths, Weaknesses and Generalizations, in Proc. 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press (1998) 332–342.  
  3. A. Ambainis, A. Kikusts and M. Valdats, On the class of languages recognizable by 1–way quantum finite automata, in Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science. Lect. Notes Comput. Sci.2010 (2001) 305–316.  
  4. A. Bertoni and M. Carpentieri, Regular languages accepted by quantum automata. Inform. Comput.165 (2001) 174–182.  
  5. A. Bertoni, C. Mereghetti and B. Palano, Quantum computing: 1-way quantum automata, in Proc. 7th International Conference on Developments in Language Theory. Lect. Notes Comput. Sci.2710 (2003) 1–20.  
  6. A. Bertoni, C. Mereghetti and B. Palano, Golomb Rulers and Difference Sets for Succinct Quantum Automata. Int. J. Found. Comp. Sci.14 (2003) 871–888.  
  7. A. Bertoni, C. Mereghetti and B. Palano, Small size quantum automata recognizing some regular languages. Theoret. Comput. Sci.340 (2005) 394–407.  
  8. A. Bertoni, C. Mereghetti and B. Palano, Some formal tools for analyzing quantum automata. Theoret. Comput. Sci.356 (2006) 14–25.  
  9. A. Brodsky and N. Pippenger, Characterizations of 1-Way Quantum Finite Automata. SIAM J. Comput.5 (2002) 1456–1478.  
  10. M. Golovkins and M. Kravtsev, Probabilistic Reversible Automata and Quantum Automata, in Proc. 8th International Computing and Combinatorics Conference. Lect. Notes Comput. Sci.2387 (2002) 574–583.  
  11. J. Gruska, Quantum Computing. McGraw-Hill (1999).  
  12. J. Gruska, Descriptional complexity issues in quantum computing. J. Automata, Languages and Combinatorics5 (2000) 191–218.  
  13. J. Hopcroft and J. Ullman, Formal Languages and Their Relation to Automata. Addison-Wesley (1969).  
  14. A. Kondacs and J. Watrous, On the Power of Quantum Finite State Automata, in Proc. 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press (1997) 66–75.  
  15. C. Moore and J. Crutchfield, Quantum automata and quantum grammars. Theoret. Comput. Sci.237 (2000) 275–306.  
  16. M. Marcus and H. Minc, Introduction to Linear Algebra. The Macmillan Company (1965). Reprinted by Dover (1988).  
  17. M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964). Reprinted by Dover (1992).  
  18. C. Mereghetti and B. Palano, On the Size of One-way Quantum Finite Automata with periodic behaviors. RAIRO-Inf. Theor. Appl.36 (2002) 277–291.  
  19. C. Mereghetti, B. Palano and G. Pighizzini, Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO-Inf. Theor. Appl.35 (2001) 477–490.  
  20. A. Nayak, Optimal lower bounds for quantum automata and random access codes, in Proc. 40th Symposium on Foundations of Computer Science (1999) 369–376.  
  21. J.E. Pin, On Languages Accepted by finite reversible automata, in Proc. 14th Int. Coll. Automata, Languages and Programming.Lect. Notes Comput. Sci.267 (1987) 237–249.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.