[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Multi-head Watson–Crick Quantum Finite Automata

  • Conference paper
  • First Online:
Emerging Technologies in Data Mining and Information Security

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1286))

  • 953 Accesses

Abstract

Watson–Crick quantum finite automata were introduced by Ganguly et al. by combining properties of DNA and Quantum automata. In this paper, we introduce a multi-head version of the above automaton. We further show that the multi-head variant is computationally more powerful than one-way multi-head reversible finite automata. In fact, we also show that the multi-head variant accepts a language which is not accepted by any one-way multi-head deterministic finite automata.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 143.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 179.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973)

    Google Scholar 

  2. Morita, K.: Two-way reversible multi-head finite automata. Fundam. Inf. 110(1), 241–254 (2011)

    Google Scholar 

  3. Kutrib, M., Malcher, A.: One-way reversible multi-head finite automata. Theor. Comput. Sci. 682, 149–164 (2017)

    Google Scholar 

  4. Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weakness and generalizations. In: IEEE 39th Annual Symposium on Foundations of Computer Science, pp. 332–342 (1998)

    Google Scholar 

  5. Ganguly, D., Chatterjee, K., Ray, K.S.: Watson-Crick quantum finite automata. Acta Inf. (2020)

    Google Scholar 

  6. Freund, R., Paun, G., Rozenberg, G., Salomaa, A.: Wason-Crick finite automata. In: DNA Based Computers III, pp. 297–327. American Mathematical Society (1999)

    Google Scholar 

  7. Bhatia, A.S., Kumar, A.: On the power of two-way multihead quantum finite automata. RAIRO-Theor. Inf. Appl. 53, 19–35 (2019). https://doi.org/10.1051/ita/2018020.

  8. Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami, Florida, pp. 66–75 (1997)

    Google Scholar 

  9. Yao, A.C., Rivest, R.L.: k+1 heads are better than k. J. ACM (JACM) 25, 337–340 (1978)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Government College of Engineering and Leather Technology, Block-LB, Sector–III, Kolkata, 700106, India

    Debayan Ganguly

  2. Government College of Engineering and Ceramic Technology, Kolkata, 700010, India

    Kingshuk Chatterjee

  3. Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata, 700108, India

    Kumar Sankar Ray

Authors
  1. Debayan Ganguly
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kingshuk Chatterjee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kumar Sankar Ray
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Debayan Ganguly .

Editor information

Editors and Affiliations

  1. Faculty of Computers and Information Technology, Cairo University, Giza, Egypt

    Aboul Ella Hassanien

  2. Rajnagar Mahavidyalaya, Birbhum, India

    Siddhartha Bhattacharyya

  3. Institute of Engineering and Management, Kolkata, West Bengal, India

    Satyajit Chakrabati

  4. Institute of Engineering and Management, Kolkata, West Bengal, India

    Abhishek Bhattacharya

  5. Institute of Engineering and Management, Kolkata, West Bengal, India

    Soumi Dutta

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ganguly, D., Chatterjee, K., Ray, K.S. (2021). Multi-head Watson–Crick Quantum Finite Automata. In: Hassanien, A.E., Bhattacharyya, S., Chakrabati, S., Bhattacharya, A., Dutta, S. (eds) Emerging Technologies in Data Mining and Information Security. Advances in Intelligent Systems and Computing, vol 1286. Springer, Singapore. https://doi.org/10.1007/978-981-15-9927-9_60

Download citation

Publish with us

Policies and ethics

Search

Navigation