Publications

Journal papers

• Michal Hospodár: Power, positive closure, and quotients on convex languages. Theoretical Computer Science 870 (2021), pp. 53–74, Elsevier
  Preliminary versions:
  • Descriptional Complexity of Power and Positive Closure on Convex Languages. In: Michal Hospodár, Galina Jirásková (eds.): Implementation and Application of Automata – 24th International Conference, CIAA 2019, Košice, Slovakia, July 22-25, 2019, Proceedings. LNCS 11601, Springer, pp. 158-170 (2019) ISBN 978-3-030-23678-6 (100%)
  • Michal Hospodár, Matúš Palmovský: Nondeterministic complexity of power and positive closure on subclasses of convex languages. In: Rudolf Freund, Michal Hospodár, Galina Jirásková, and Giovanni Pighizzini (eds.): Tenth Workshop on Non-Classical Models of Automata and Applications, NCMA 2018, Košice, Slovakia, August 21-22, 2018. Short Papers. Wien: Institut für Computersprachen TU Wien, pp. 35-44 (2018)
• Michal Hospodár (50%), Markus Holzer: The ranges of accepting state complexities of languages resulting from some operations. International Journal of Foundations of Computer Science 31:08, (2020), pp. 1159–1177, World Scientific
  Preliminary version:
  • The Ranges of Accepting State Complexities of Languages Resulting From Some Operations. In: Cezar Câmpeanu (ed.): Implementation and Application of Automata – 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 – August 2, 2018, Proceedings. LNCS 10977, Springer, pp. 198–210 (2018) ISBN 978-3-319-94811-9 (50%)
• Michal Hospodár (34%), Galina Jirásková, Peter Mlynárčik: Nondeterministic complexity in subclasses of convex languages. Theoretical Computer Science 787 (2019) pp. 89-110, Elsevier
  Preliminary version:
  • Nondeterministic Complexity of Operations on Closed and Ideal Languages. In: Yo-Sub Han, Kai Salomaa (eds.): Implementation and Application of Automata – 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings. LNCS 9705, Springer, pp. 125–137 (2016) ISBN 978-3-319-40945-0 (33%)
  • Nondeterministic Complexity of Operations on Free and Convex Languages. In: Arnaud Carayol, Cyril Nicaud (eds.): Implementation and Application of Automata – 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings. LNCS 10329, Springer, pp. 138–150 (2017) ISBN 978-3-319-60133-5 (34%)
• Michal Hospodár, Galina Jirásková (34%), Peter Mlynárčik: Descriptional complexity of the forever operator. International Journal of Foundations of Computer Science 30:01, (2019), pp. 115–134, World Scientific
  Preliminary version:
  • On the Descriptive Complexity of $$\overline{\varSigma^*\overline{L}}$$. In: Émilie Charlier, Julien Leroy, Michel Rigo (eds.): Developments in Language Theory – 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. LNCS 10396, Springer, pp. 222–234 (2017) ISBN 978-3-319-62808-0 (34%)
• Michal Hospodár (50%), Galina Jirásková: The complexity of concatenation on deterministic and alternating finite automata. RAIRO – Theoretical Informatics and Applications 52 (2018), pp. 153–168, EDP Sciences
  Preliminary version:
  • Concatenation on deterministic and alternating automata. In: Henning Bordihn, Rudolf Freund, Benedek Nagy, and György Vaszil (eds.): Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29-30, 2016. Proceedings. books@ocg.at, vol. 321, Wien: Österreichische Computer Gesellschaft, pp. 179–194 (2016) ISBN 978-3-903035-10-2

Conference and workshop papers

• Michal Hospodár, Peter Mlynárcik, Viktor Olejár: Operations on Subregular Languages and Nondeterministic State Complexity. In: Descriptional Complexity of Formal Systems - DCFS 2022 - 24th IFIP WG 1.02 International Conference, Debrecen, Hungary, August 29–31, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13439, Springer, pp. 112–126 (2022)
• Michal Hospodár, Viktor Olejár: The Cut Operation in Subclasses of Convex Languages (Extended Abstract). In: Implementation and Application of Automata - CIAA 2022 - 26th International Conference, Rouen, France, June 28 – July 1, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13266, Springer, pp. 152–164 (2022)
• Michal Hospodár (60%), Peter Mlynárčik: Operations on Permutation Automata. In: Nataša Jonoska, Dmytro Savchuk (eds.): Developments in Language Theory. DLT 2020. Lecture Notes in Computer Science, vol 12086. Springer, pp. 122–136 (2020) ISBN 978-3-030-48515-3
• Sylvie Davies, Michal Hospodár (50%): Square, Power, Positive Closure, and Complementation on Star-Free Languages. In: Michal Hospodár, Galina Jirásková, Stavros Konstantinidis (eds.): Descriptional Complexity of Formal Systems – 21th IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, Proceedings. LNCS 11612, Springer, pp. 98–110 (2019) ISBN 978-3-030-23246-7
  Preliminary version:
  • Michal Hospodár: Complexity of unary union-free and unary star-free languages. In: Henning Bordihn, Rudolf Freund, Benedek Nagy, and György Vaszil (eds.): Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29-30, 2016. Short Papers. Wien: Institut für Computersprachen TU Wien, pp. 15–23 (2016) ISBN 978-3-200-04725-9
• Markus Holzer, Michal Hospodár (50%): The Range of State Complexities of Languages Resulting from the Cut Operation. In: Carlos Martín-Vide, Alexander Okhotin, Dana Shapira (eds.): Language and Automata Theory and Applications. 13th International Conference, LATA 2019, Saint Petersburg, Russia, March 26-29, 2019, Proceedings. LNCS 11417, Springer, pp. 190–202 (2019) ISBN 978-3-030-13434-1
  Preliminary versions:
  • Complexity of languages resulting from the cut operation in the unary case. In: Rudolf Freund, Michal Hospodár, Galina Jirásková, and Giovanni Pighizzini (eds.): Tenth Workshop on Non-Classical Models of Automata and Applications, NCMA 2018, Košice, Slovakia, August 21-22, 2018. Short Papers. Wien: Institut für Computersprachen TU Wien, pp. 25–34 (2018)
  • On the Magic Number Problem of the Cut Operation. Technical Report 1703. Gießen: Justus-Liebeig-Universität (2017) http://www.informatik.uni-giessen.de/reports/Report1703.pdf
• Michal Hospodár (34%), Galina Jirásková, Ivana Krajňáková: Operations on Boolean and Alternating Automata. In: Fedor V. Fomin, Vladimir V. Podolskii (eds.): Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings. LNCS 10846, Springer, pp. 181–193 (2018) ISBN 978-3-319-90529-7
• Michal Hospodár: The Story of Concatenation. In: Černý's Conjecture and Optimization Problems on Finite Automata (proceedings), Opava: Slezská univerzita (submitted September 2017, never published)
  Abstract:
  • The Story of Concatenation. In: Ján Buša, Jozef Doboš (eds.): 18. Konferencia košických matematikov, Herlany, 20.–22. apríla 2017. Proceedings. Košice: JSMF, PF UPJŠ, FEI TUKE, pp. 20–21 (2017) ISBN 978-80-553-3146-1

Other publications

• Michal Hospodár, Galina Jirásková (34%), Peter Mlynárčik: A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity. In: Hans-Joachim Böckenhauer, Dennis Komm, Walter Unger: Adventures Between Lower Bounds and Higher Altitudes – Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday. LNCS 11011, Springer, pp. 17–32 (2018) ISBN 978-3-319-98354-7