Improved Constructions for Succinct Affine Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

Improved Constructions for Succinct Affine Automata

  • Conference paper
  • First Online:
Descriptional Complexity of Formal Systems (DCFS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13037))

Included in the following conference series:

Abstract

Affine finite automata (AfAs) can be more succinct than probabilistic and quantum finite automata when recognizing some regular languages with bounded error. In this paper, we improve previously known succinct AFA constructions in three ways. First, we replace some of the fixed error bounds with arbitrarily small error bounds. Second, we present new constructions by using fewer states than the previous constructions. Third, we show that any language recognized by a nondeterministic finite automaton (NFA) is also recognized by bounded-error AfAs having one more state, and so, AfAs inherit all succinct results by NFAs. As a special case, we also show that any language recognized by an NFA is recognized by AfAs with zero error if the number of accepting path(s) for each member is the same number.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6863
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8579
Price includes VAT (Japan)
  • 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

Notes

  1. 1.

    We refer the reader to [8] for certain discussions about interference with historical remarks.

  2. 2.

    We use lowercase “f” to differentiate AfAs from PFAs or QFAs due to its non-linear behavior.

  3. 3.

    See [11] for the details about using end-markers and generalized versions of AfAs.

References

  1. Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: FOCS’98, pp. 332–341. IEEE (1998)

    Google Scholar 

  2. Ambainis, A.: The complexity of probabilistic versus deterministic finite automata. In: Asano, T., Igarashi, Y., Nagamochi, H., Miyano, S., Suri, S. (eds.) ISAAC 1996. LNCS, vol. 1178, pp. 233–238. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0009499

  3. Ambainis, A., Yakaryılmaz, A.: Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112(7), 289–291 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ambainis, A., Yakaryılmaz, A.: Automata and quantum computing. In: Éric Pin, J. (ed.) Handbook of Automata Theory, vol. 2, chap. 39, pp. 1457–1493. European Mathematical Society Publishing House (2021)

    Google Scholar 

  5. Belovs, A., Montoya, J.A., Yakaryılmaz, A.: On a conjecture by Christian Choffrut. Int. J. Found. Comput. Sci. 28(5), 483–502 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  6. Díaz-Caro, A., Yakaryılmaz, A.: Affine Computation and Affine Automaton. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 146–160. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-34171-2_11

  7. Geffert, V., Yakaryılmaz, A.: Classical automata on promise problems. Discrete Math. Theoret. Comput. Sci. 17(2), 157–180 (2015)

    MathSciNet  MATH  Google Scholar 

  8. Hirvensalo, M.: Interference as a computational resource: a tutorial. Nat. Comput. 17(1), 201–219 (2017). https://doi.org/10.1007/s11047-017-9654-x

    Article  MathSciNet  MATH  Google Scholar 

  9. Hirvensalo, M., Moutot, E., Yakaryılmaz, A.: On the Computational power of affine automata. In: Drewes, F., Martín-Vide, C., Truthe, B. (eds.) LATA 2017. LNCS, vol. 10168, pp. 405–417. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53733-7_30

  10. Hirvensalo, M., Moutot, E., Yakaryılmaz, A.: Computational Limitations of Affine Automata. In: McQuillan, I., Seki, S. (eds.) UCNC 2019. LNCS, vol. 11493, pp. 108–121. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19311-9_10

  11. Hirvensalo, M., Moutot, E., Yakaryılmaz, A.: computational limitations of affine automata and generalized affine automata. Nat. Comput. 20(1), 1–12 (2021). https://doi.org/10.1007/s11047-020-09815-1

  12. Ibrahimov, R., Khadiev, K., Prūsis, K., Yakaryılmaz, A.: Error-Free Affine, Unitary, and Probabilistic OBDDs. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 175–187. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94631-3_15

  13. Ibrahimov, R., Khadiev, K., Prūsis, K., Yakaryılmaz, A.: Error-free affine, unitary, and probabilistic OBDDs. Int. J. Found. Comput. Sci. (2021). https://doi.org/10.1142/S0129054121500246

    Article  MathSciNet  MATH  Google Scholar 

  14. Khadieva, A., Yakaryılmaz, A.: Affine automata verifiers. In: Kostitsyna, I., Orponen, P. (eds.) UCNC 2021. LNCS, vol. 12984, pp. 84–100. Springer, Cham (2021)

    Google Scholar 

  15. Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: STOC’00: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 644–651 (2000)

    Google Scholar 

  16. Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS 1997, pp. 66–75 (1997)

    Google Scholar 

  17. Li, L., Qiu, D., Zou, X., Li, L., Wu, L., Mateus, P.: Characterizations of one-way general quantum finite automata. Theoret. Comput. Sci. 419, 73–91 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  18. Nakanishi, M., Khadiev, K., Prūsis, K., Vihrovs, J., Yakaryılmaz, A.: Exact affine counter automata. In: 15th International Conference on Automata and Formal Languages. EPTCS, vol. 252, pp. 205–218 (2017). arXiv:1703.04281

  19. Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)

    MATH  Google Scholar 

  20. Rabin, M.O.: Probabilistic automata. Inf. Control 6, 230–243 (1963)

    Article  MATH  Google Scholar 

  21. Say, A.C.C., Yakaryılmaz, A.: Quantum finite automata: a modern introduction. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Computing with New Resources. LNCS, vol. 8808, pp. 208–222. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13350-8_16

    Chapter  MATH  Google Scholar 

  22. Turakainen, P.: Generalized automata and stochastic languages. Proc. Am. Math. Soc. 21, 303–309 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  23. Villagra, M., Yakaryılmaz, A.: Language recognition power and succinctness of affine automata. In: Amos, M., Condon, A. (eds.) UCNC 2016. LNCS, vol. 9726, pp. 116–129. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41312-9_10

    Chapter  MATH  Google Scholar 

  24. Villagra, M., Yakaryılmaz, A.: Language recognition power and succinctness of affine automata. Nat. Comput. 17(2), 283–293 (2017). https://doi.org/10.1007/s11047-017-9652-z

    Article  MathSciNet  MATH  Google Scholar 

  25. Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quant. Inf. Comput. 10(9 & 10), 747–770 (2010)

    MathSciNet  MATH  Google Scholar 

  26. Yakaryılmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theoret. Comput. Sci. 12(2), 19–40 (2010)

    MathSciNet  MATH  Google Scholar 

  27. Yakaryılmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Inf. Comput. 279(6), 873–892 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Yakaryılmaz was partially supported by the ERDF project Nr. 1.1.1.5/19/A/005 “Quantum computers with constant memory”.

We thank anonymous reviewers for their helpful corrections and suggestions.

Author information

Authors and Affiliations

  1. Center for Quantum Computer Science, University of Latvia, Rīga, Latvia

    Abuzer Yakaryılmaz

  2. QWorld Association, Tallinn, Estonia

    Abuzer Yakaryılmaz

  3. Department of Mathematics and Statistics, University of Turku, Turku, Finland

    Abuzer Yakaryılmaz

Authors
  1. Abuzer Yakaryılmaz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Abuzer Yakaryılmaz .

Editor information

Editors and Affiliations

  1. Yonsei University, Seoul, Korea (Republic of)

    Yo-Sub Han

  2. Kangwon National University, Chuncheon, Korea (Republic of)

    Sang-Ki Ko

Rights and permissions

Reprints and permissions

Copyright information

© 2021 IFIP International Federation for Information Processing

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yakaryılmaz, A. (2021). Improved Constructions for Succinct Affine Automata. In: Han, YS., Ko, SK. (eds) Descriptional Complexity of Formal Systems. DCFS 2021. Lecture Notes in Computer Science(), vol 13037. Springer, Cham. https://doi.org/10.1007/978-3-030-93489-7_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-93489-7_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-93488-0

  • Online ISBN: 978-3-030-93489-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships