References

  1. J.A. Brzozowski & E.L. Leiss (1980): On equations for regular languages, finite automata, and sequential networks. Theor. Comput. Sci. 10, pp. 19–35, doi:10.1016/0304-3975(80)90069-9.
  2. A.K. Chandra, D. Kozen & L.J. Stockmeyer (1981): Alternation. J. ACM 28(1), pp. 114–133, doi:10.1145/322234.322243.
  3. Abdelaziz Fellah, Helmut Jürgensen & Sheng Yu (1990): Constructions for alternating finite automata. Int. J. Comput. Math. 35(1-4), pp. 117–132, doi:10.1080/00207169008803893.
  4. M. Hospodár (2021): Power, positive closure, and quotients on convex languages. Theor. Comput. Sci. 870, pp. 53–74, doi:10.1016/j.tcs.2021.02.002.
  5. M. Hospodár & G. Jirásková (2018): The complexity of concatenation on deterministic and alternating finite automata. RAIRO Theor. Informatics Appl. 52(2-3-4), pp. 153–168, doi:10.1051/ita/2018011.
  6. M. Hospodár, G. Jirásková & I. Krajňáková (2018): Operations on Boolean and alternating finite automata. In: F.V. Fomin & V.V. Podolskii: CSR 2018, LNCS, vol. 10846. Springer, pp. 181–193, doi:10.1007/978-3-319-90530-3_16.
  7. G. Jirásková (2012): Descriptional complexity of operations on alternating and Boolean automata. In: E.A. Hirsch, J. Karhumäki, A. Lepistö & M. Prilutskii: CSR 2012, LNCS, vol. 7353. Springer, pp. 196–204, doi:10.1007/978-3-642-30642-6_19.
  8. G. Jirásková & I. Krajňáková (2019): Square on deterministic, alternating, and Boolean finite automata. Int. J. Found. Comput. Sci. 30(6-7), pp. 1117–1134, doi:10.1142/S0129054119400318.
  9. G. Jirásková & J. Šebej (2012): Reversal of binary regular languages. Theor. Comput. Sci. 449, pp. 85–92, doi:10.1016/j.tcs.2012.05.008.
  10. D. Kozen (1976): On parallelism in Turing machines. In: 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976. IEEE Computer Society, pp. 89–97, doi:10.1109/SFCS.1976.20.
  11. I. Krajňáková (2020): Finite Automata and Operational Complexity. Comenius University in Bratislava, Faculty of Mathematics, Physics and Informatics. Available at https://www.mat.savba.sk/musav/autoreferaty/Krajnakova-dizertacna_praca.pdf.
  12. E.L. Leiss (1981): Succint representation of regular languages by Boolean automata. Theor. Comput. Sci. 13, pp. 323–330, doi:10.1016/S0304-3975(81)80005-9.
  13. A. N. Maslov (1970): Estimates of the number of states of finite automata. Soviet Math. Doklady 11(5), pp. 1373–1375. Available at https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=35742&option_lang=eng.
  14. M. Palmovský (2016): Kleene closure and state complexity. RAIRO Theor. Informatics Appl. 50(3), pp. 251–261, doi:10.1051/ita/2016024.
  15. S. Yu (1997): Regular Languages. In: G. Rozenberg & A. Salomaa: Handbook of Formal Languages, Volume 1: Word, Language, Grammar. Springer, pp. 41–110, doi:10.1007/978-3-642-59136-5_2.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org