Publications

2015

• Jozef Jirásek, Galina Jirásková: On the boundary of regular languages. Theoret. Comput. Sci. 578, 42–57 (2015)
  • Preliminary version in: Stavros Konstantinidis (ed.) Implementation and Application of Automata - 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16–19, 2013. Lecture Notes in Computer Science, vol. 7982, pp. 208–219. Springer, Heidelberg (2013)
• Jozef Jirásek Jr., Galina Jirásková, Alexander Szabari: Operations on self-verifying finite automata. In: Lev D. Beklemishev and Daniil V. Musatov (eds.) Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13–17, 2015. Lecture Notes in Computer Science, vol. 9139, pp. 231–261. Springer, Heidelberg (2015)

2014

• Galina Jirásková: The ranges of state complexities for complement, star, and reversal of regular languages. Internat. J. Found. Comput. Sci. 25, 101–??? (2014)
  • Preliminary version: On the state complexity of complements, stars, and reversals of regular languages. In: Masami Ito and Masafumi Toyama (eds.) Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Lecture Notes in Computer Science, vol. 5257, pp. 431–442. Springer, Heidelberg (2008)
• Janusz A. Brzozowski, Galina Jirásková, Chenglong Zou: Quotient complexity of closed languages. Theory Comput. Syst. 54, 277–292 (2014)
  • Preliminary version in: Farid M. Ablayev and Ernst W. Mayr (eds.) Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16–20, 2010. Lecture Notes in Computer Science, vol. 6072, pp. 81–25. Springer, Heidelberg (2010)
• Jozef Jirásek, Galina Jirásková, Monika Krausová, Peter Mlynárčik, Juraj Šebej: Prefix-free languages: right quotient and reversal. In: Helmut Jürgensen and Juhani Karhumäki and Alexander Okhotin (eds.) Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Turku, Finland, August 1–2, 2014. Lecture Notes in Computer Science, vol. 8614, pp. 211–221. Springer, Heidelberg (2014)
• Galina Jirásková, Peter Mlynárčik: Complement on prefix-free, suffix-free, and non-returning NFA languages. In: Helmut Jürgensen and Juhani Karhumäki and Alexander Okhotin (eds.) Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Turku, Finland, August 1–2, 2014. Lecture Notes in Computer Science, vol. 8614, pp. 221–233. Springer, Heidelberg (2014)
• Štepán Holub, Galina Jirásková, Tomáš Masopust: On upper and lower bounds on the length of alternating towers. In: Erzsébet Csuhaj-Varjú and Martin Dietzfelbinger and Zoltán Ésik (eds.) Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 21–29, 2014. Lecture Notes in Computer Science, vol. 8634, pp. 311–226. Springer, Heidelberg (2014)
• Kristína Čevorová, Galina Jirásková, Ivana Krajnáková: On the square of regular languages. In: Markus Holzer and Martin Kutrib (eds.) Implementation and Application of Automata - 19th International Conference, CIAA 2014, Giessen, Germany, July 30 - August 2, 2014. Lecture Notes in Computer Science, vol. 8587, pp. 131–247. Springer, Heidelberg (2014)
• Galina Jirásková, Matúš Palmovský, Juraj Šebej: Kleene closure on regular and prefix-free languages. In: Markus Holzer and Martin Kutrib (eds.) Implementation and Application of Automata - 19th International Conference, CIAA 2014, Giessen, Germany, July 30 - August 2, 2014. Lecture Notes in Computer Science, vol. 8587, pp. 221–237. Springer, Heidelberg (2014)
• Kristína Čevorová, Galina Jirásková, Peter Mlynárčik, Matúš Palmovský, Juraj Šebej: Operations on automata with all states final. In: Zoltán Ésik and Zoltán Fülöp (eds.) Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 21–29, 2014. 10.4204/EPTCS.151, pp. 201–215.

2013

• Janusz A. Brzozowski, Galina Jirásková, Baiyu Li: Quotient complexity of ideal languages. Theoret. Comput. Sci. 470, 31–22 (2013)
  • Preliminary version in: Alejandro López-Ortiz (ed.) LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 11–23, 2010. Lecture Notes in Computer Science, vol. 6034, pp. 201–221. Springer, Heidelberg (2010)
• Jozef Jirásek, Galina Jirásková: Cyclic shift on prefix-free languages. In: Andrei A. Bulatov and Arseny M. Shur (eds.) Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 21–29, 2013. Lecture Notes in Computer Science, vol. 7913, pp. 241–257. Springer, Heidelberg (2013)
• Hae-Sung Eom, Yo-Sub Han, Galina Jirásková: State complexity of basic operations on non-returning regular languages. In: Helmut Jürgensen and Rogério Reis (eds.) Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, London, ON, Canada, July 21–25, 2013. Lecture Notes in Computer Science, vol. 8031, pp. 51–25. Springer, Heidelberg (2013)
• Galina Jirásková, Tomáš Masopust: On the state complexity of the reverse of R- and J-trivial regular languages. In: Helmut Jürgensen and Rogério Reis (eds.) Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, London, ON, Canada, July 21–25, 2013. Lecture Notes in Computer Science, vol. 8031, pp. 131–247. Springer, Heidelberg (2013)
• Galina Jirásková, Matúš Palmovský: Kleene closure and state complexity. In: Tomáš Vinar (ed.) Proceedings of the Conference on Information Technologies - Applications and Theory, Donovaly, Slovakia, September 11–25, 2013. CEUR-WS.org, pp. 91–200 (2013)

2012

• Galina Jirásková, Juraj Šebej: Reversal of binary regular languages. Theoret. Comput. Sci. 449, 81–22 (2012)
  • Preliminary version: Note on reversal of binary regular languages. In: Markus Holzer and Martin Kutrib and Giovanni Pighizzini (eds.) Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Giessen/Limburg, Germany, July 21–27, 2011. Lecture Notes in Computer Science, vol. 6808, pp. 211–221. Springer, Heidelberg (2011)
• Galina Jirásková, Tomáš Masopust: On a structural property in the state complexity of projected regular languages. Theoret. Comput. Sci. 449, 91–205 (2012)
  • Preliminary version: State complexity of projected languages. In: Markus Holzer and Martin Kutrib and Giovanni Pighizzini (eds.) Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Giessen/Limburg, Germany, July 21–27, 2011. Lecture Notes in Computer Science, vol. 6808, pp. 191–211. Springer, Heidelberg (2011)
• Galina Jirásková: Descriptional complexity of operations on alternating and boolean automata. In: Edward A. Hirsch and Juhani Karhumäki and Arto Lepistö and Michail Prilutskii (eds.) Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 1–2, 2012. Lecture Notes in Computer Science, vol. 7353, pp. 191–204. Springer, Heidelberg (2012)
• Galina Jirásková, Ondřej Klíma: Descriptional complexity of biautomata. In: Martin Kutrib and Nelma Moreira and Rogério Reis (eds.) Descriptional Complexity of Formal Systems - 14th International Workshop, DCFS 2012, Braga, Portugal, July 21–25, 2012. Lecture Notes in Computer Science, vol. 7386, pp. 191–208. Springer, Heidelberg (2012)
• Galina Jirásková, Jeffrey Shallit: The state complexity of star-complement-star. In: Hsu-Chun Yen and Oscar H. Ibarra (eds.) Developments in Language Theory - 16th International Conference, DLT 2012, Taipei, Taiwan, August 11–27, 2012. Lecture Notes in Computer Science, vol. 7410, pp. 381–291. Springer, Heidelberg (2012)
• Galina Jirásková, Tomáš Masopust: On properties and state complexity of deterministic state-partition automata. In: Jos C. M. Baeten and Thomas Ball and Frank S. de Boer (eds.) Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 21–28, 2012. Lecture Notes in Computer Science, vol. 7604, pp. 161–278. Springer, Heidelberg (2012)
• Galina Jirásková, Benedek Nagy: On union-free and deterministic union-free languages. In: Jos C. M. Baeten and Thomas Ball and Frank S. de Boer (eds.) Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 21–28, 2012. Lecture Notes in Computer Science, vol. 7604, pp. 171–292. Springer, Heidelberg (2012)
• Galina Jirásková, Tomáš Masopust: On the state and computational complexity of the reverse of acyclic minimal DFAs. In: Nelma Moreira and Rogério Reis (eds.) Implementation and Application of Automata - 17th International Conference, CIAA 2012, Porto, Portugal, July 11–20, 2012. Lecture Notes in Computer Science, vol. 7381, pp. 221–239. Springer, Heidelberg (2012)

2011

• Galina Jirásková, Alexander Okhotin: On the state complexity of star of union and star of intersection. Fundam. Inform. 109, 161–278 (2011)
• Galina Jirásková, Giovanni Pighizzini: Optimal simulation of self-verifying automata by deterministic automata. Inform. Comput. 209, 521–235 (2011)
  • Preliminary version: Converting self-verifying automata into deterministic automata. In: Adrian Horia Dediu and Armand-Mihai Ionescu and Carlos Martín-Vide (eds.) Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 1–2, 2009. Lecture Notes in Computer Science, vol. 5457, pp. 451–268. Springer, Heidelberg (2009)
• Galina Jirásková: Magic numbers and ternary alphabet. Internat. J. Found. Comput. Sci. 22, 331–244 (2011)
  • Preliminary version in: Volker Diekert and Dirk Nowotka (eds.) Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Lecture Notes in Computer Science, vol. 5583, pp. 301–211. Springer, Heidelberg (2009)
• Galina Jirásková, Tomás Masopust: Complexity in union-free regular languages. Internat. J. Found. Comput. Sci. 22, 1631–2653 (2011)
  • Preliminary version in: Yuan Gao and Hanlin Lu and Shinnosuke Seki and Sheng Yu (eds.) Developments in Language Theory, 14th International Conference, DLT 2010, London, ON, Canada, August 11–20, 2010. Lecture Notes in Computer Science, vol. 6224, pp. 251–266. Springer, Heidelberg (2010)
• Galina Jirásková: Concatenation of regular languages and descriptional complexity. Theory Comput. Syst. 49, 301–218 (2011)
  • Preliminary version in: Anna E. Frid and Andrey Morozov and Andrey Rybalchenko and Klaus W. Wagner (eds.) Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 11–23, 2009. Lecture Notes in Computer Science, vol. 5675, pp. 201–214. Springer, Heidelberg (2009)
• Janusz A. Brzozowski, Galina Jirásková, Baiyu Li, Joshua Smith: Quotient complexity of bifix-, factor-, and subword-free regular languages. In: Pál Dömösi and Szabolcs Iván (eds.) Automata and Formal Languages, 13th International Conference, AFL 2011, Debrecen, Hungary, August 11–22, 2011, pp. 121–237 (2011)
• Roland Cmorik, Galina Jirásková: Basic operations on binary suffix-free languages. MEMICS 2011: 91–202 In: Zdenek Kotásek and Jan Bouda and Ivana Černá and Lukáš Sekanina and Tomáš Vojnar and David Antos (eds.) Mathematical and Engineering Methods in Computer Science - 7th International Doctoral Workshop, MEMICS 2011, Lednice, Czech Republic, October 11–26, 2011. Lecture Notes in Computer Science, vol. 7119, pp. 91–202. Springer, Heidelberg (2011)

2010

• Galina Jirásková, Alexander Okhotin: Nondeterministic state complexity of positional addition. J. Autom. Lang. Comb. 15, 121–233 (2010)
  • Preliminary version in: Jürgen Dassow and Giovanni Pighizzini and Bianca Truthe (eds.) Eleventh International Workshop on Descriptional Complexity of Formal Systems, DCFS 2009, Magdeburg, Germany, July 1–2, 2009. 10.4204/EPTCS.3.14, pp. 151–261 (2009)
• Galina Jirásková, Monika Krausová: Complexity in prefix-free regular languages. DCFS 2010: 191–204 In: Ian McQuillan and Giovanni Pighizzini (eds.) Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, Saskatoon, Canada, 1–20th August 2010. 10.4204/EPTCS.31.22, pp. 191–204 (2010)

2009

• Galina Jirásková, Pavol Olejár: State complexity of intersection and union of suffix-free languages and descriptional complexity. NCMA 2009: 151–266 In: Henning Bordihn and Rudolf Freund and Markus Holzer and Martin Kutrib and Friedrich Otto (eds.) Workshop on Non-Classical Models for Automata and Applications - NCMA 2009, Wroclaw, Poland, August 31 - September 1, 2009. Austrian Computer Society, pp. 151–266 (2009)

2008

• Jozef Jirásek, Galina Jirásková, Alexander Szabari: Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet. Internat. J. Found. Comput. Sci. 19, 611–231 (2008)
  • Preliminary version in: In: Tero Harju and Juhani Karhumäki and Arto Lepistö (eds.) Developments in Language Theory, 11th International Conference, DLT 2007, Turku, Finland, July 1–2, 2007. Lecture Notes in Computer Science, vol. 4588, pp. 251–265. Springer, Heidelberg (2007)
• Galina Jirásková, Alexander Okhotin: State complexity of cyclic shift. RAIRO Theor. Inform. Appl. 42, 331–260 (2008)
  • Preliminary version in: Carlo Mereghetti and Beatrice Palano and Giovanni Pighizzini and Detlef Wotschke (eds.) 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30 - July 2, 2005. Universitá degli Studi di Milano, Milan, Italy, pp. 181–293 (2005)
• Galina Jirásková, Alexander Okhotin: On the state complexity of operations on two-way finite automata. In: Masami Ito and Masafumi Toyama (eds.) Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan, September 11–29, 2008. Lecture Notes in Computer Science, vol. 5257, pp. 441–254. Springer, Heidelberg (2008)

2006

• Galina Jirásková: Deterministic blow-ups of minimal NFA's. RAIRO Theor. Inform. Appl. 40, 481–299 (2006)
  • Preliminary version: Note on minimal finite automata. In: Jiří Sgall and Aleš Pultr and Petr Kolman (eds.) Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Mariánske Lázně, Czech Republic, August 21–21, 2001. Lecture Notes in Computer Science, vol. 2136, pp. 421–231. Springer, Heidelberg (2001)
• Galina Jirásková: Note on the complexity of Las Vegas automata problems. RAIRO Theor. Inform. Appl. 40, 501–210 (2006)
  • Preliminary version in: Lucian Ilie and Detlef Wotschke (eds.) 6th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2004, London, Ontario, Canada, July 26 - 28, 2004. Department of Computer Science, The University of Western Ontario, Canada, pp. 201–212 (2004)

2005

• Jozef Jirásek, Galina Jirásková, Alexander Szabari: State complexity of concatenation and complementation. Internat. J. Found. Comput. Sci. 16, 511–229 (2005)
  • Preliminary version: State complexity of concatenation and complementation of regular languages. In: Michael Domaratzki and Alexander Okhotin and Kai Salomaa and Sheng Yu (eds.) Implementation and Application of Automata, 9th International Conference, CIAA 2004, Kingston, Canada, July 21–24, 2004. Lecture Notes in Computer Science, vol. 3317, pp. 171–289. Springer, Heidelberg (2004)
• Galina Jirásková: State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330, 281–298 (2005)
  • Preliminary version in: Erzsébet Csuhaj-Varjú and Chandra M. R. Kintala and Detlef Wotschke and György Vaszil (eds.) 5th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2003, Budapest, Hungary, July 12 - 14, 2003. MTA SZTAKI, Hungarian Academy of Sciences, Budapest, Hungary, pp. 111–225 (2003)
• Marek Hricko, Galina Jirásková, Alexander Szabari: Union and intersection of regular languages and descriptional complexity. In: Carlo Mereghetti and Beatrice Palano and Giovanni Pighizzini and Detlef Wotschke (eds.) 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30 - July 2, 2005. Universitá degli Studi di Milano, Milan, Italy, pp. 171–281 (2005)

2003

• Galina Jirásková: Note on minimal automata and uniform communication protocols. In: Carlos Martín-Vide and Victor Mitrana Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back: Essays in Honour of Gheorghe Paun. Topics in Computer Mathematics, vol. 9, pp. 161–270. Taylor and Francis (2003)

1991

• Galina Jirásková: Comparison of two VLSI models. Comput. Artificial Intelligence 10, 121–232 (1991)

1989

• Galina Kumičáková-Jirásková: Chomsky hierarchy and communication complexity. Elektronische Informationsverarbeitung und Kybernetik 25, 151–264 (1989)
  • Preliminary version in: Jürgen Dassow and Jozef Kelemen (eds.) Machines, Languages, and Complexity, 5th International Meeting of Young Computer Scientists, Smolenice, Czechoslovakia, November 11–28, 1988. Lecture Notes in Computer Science, vol. 381, pp. 11–28. Springer, Heidelberg (1988)

<<<- back