Citations

• Galina Jirásková: The ranges of state complexities for complement, star, and reversal of regular languages. Internat. J. Found. Comput. Sci. 25, 101–??? (2014)
  0. 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)
  1. Markus Holzer, Sebastian Jakobi, Martin Kutrib: The magic number problem for subregular language families. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 115–131 (2012)
• Janusz A. Brzozowski, Galina Jirásková, Chenglong Zou: Quotient complexity of closed languages. Theory Comput. Syst. 54, 277–292 (2014)
  0. 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)
  1. Markus Holzer, Martin Kutrib, Katja Meckel: Nondeterministic state complexity of star-free languages. THEORETICAL COMPUTER SCIENCE 450, 68–80 (2012)
  2. Elena Pribavkina, Emanuele Rodaro: State complexity of code operators. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 22, 1669–1681 (2011)
  3. Markus Holzer, Martin Kutrib, Katja Meckel: Nondeterministic state complexity of star-free languages. In: 16th International Conference on Implementation and Application of Automata (CIAA 2011), Univ Francois Rabelais Tours, Blois, FRANCE, JUL 13-16, 2011. Lecture Notes in Computer Science, vol. 6807, pp. 178–189 (2011)
• Janusz A. Brzozowski, Galina Jirásková, Baiyu Li: Quotient complexity of ideal languages. Theoret. Comput. Sci. 470, 31–22 (2013)
  0. 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)
  1. Martin Berglund, Henrik Bjorklund, Johanna Bjorklund: Shuffled languages-representation and recognition. THEORETICAL COMPUTER SCIENCE 489, 1–20 (2013)
  2. Juergen Dassow, Florin Manea, Bianca Truthe: Networks of evolutionary processors: the power of subregular filters. ACTA INFORMATICA 50, 41–75 (2013)
  3. Juergen Dassow, Florin Manea, Bianca Truthe: On external contextual grammars with subregular selection languages. THEORETICAL COMPUTER SCIENCE 449, 64–73 (2012)
  4. Elena Pribavkina, Emanuele Rodaro: State complexity of code operators. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 22, 1669–1681 (2011)
  5. Juergen Dassow, Florin Manea, Bianca Truthe: Networks of evolutionary processors with subregular filters. In: 5th International Conference on Language and Automata Theory and Applications, Tarragona, SPAIN, MAY 26-31, 2011. Lecture Notes in Computer Science, vol. 6638, pp. 262–273 (2011)
  6. J WACZULIK: Area time squared and area complexity of vlsi computations is strongly unclosed under union and intersection. LECTURE NOTES IN COMPUTER SCIENCE 464, 278–287 (1990)
• Galina Jirásková, Juraj Šebej: Reversal of binary regular languages. Theoret. Comput. Sci. 449, 81–22 (2012)
  0. 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)
  1. Hae-Sung Eom, Yo-Sub Han, Kai Salomaa: State complexity of k-union and k-intersection for prefix-free regular languages. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 26, 211–227 (2015)
  2. Hae-Sung Eom, Yo-Sub Han: State complexity of combined operations for suffix-free regular languages. THEORETICAL COMPUTER SCIENCE 510, 87–93 (2013)
• Galina Jirásková, Alexander Okhotin: On the state complexity of star of union and star of intersection. Fundam. Inform. 109, 161–278 (2011)
  1. Hae-Sung Eom, Yo-Sub Han: State complexity of combined operations for suffix-free regular languages. THEORETICAL COMPUTER SCIENCE 510, 87–93 (2013)
  2. Yuan Gao, Lila Kari: State complexity of star of union and square of union on k regular languages. THEORETICAL COMPUTER SCIENCE 499, 38–50 (2013)
  3. Arto Salomaa, Kai Salomaa, Sheng Yu: Undecidability of state complexity. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 90, 1310–1320 (2013)
• Galina Jirásková, Giovanni Pighizzini: Optimal simulation of self-verifying automata by deterministic automata. Inform. Comput. 209, 521–235 (2011)
  0. 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)
  1. G. Castiglione, A. Restivo, M. Sciortino: Nondeterministic moore automata and brzozowski's minimization algorithm. THEORETICAL COMPUTER SCIENCE 450, 81–91 (2012)
  2. Giusi Castiglione, Antonio Restivo, Marinella Sciortino: Nondeterministic moore automata and brzozowski's algorithm. In: 16th International Conference on Implementation and Application of Automata (CIAA 2011), Univ Francois Rabelais Tours, Blois, FRANCE, JUL 13-16, 2011. Lecture Notes in Computer Science, vol. 6807, pp. 88–99 (2011)
• Galina Jirásková: Magic numbers and ternary alphabet. Internat. J. Found. Comput. Sci. 22, 331–244 (2011)
  0. 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)
  1. Markus Holzer, Sebastian Jakobi, Martin Kutrib: The magic number problem for subregular language families. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 115–131 (2012)
• Galina Jirásková, Tomás Masopust: Complexity in union-free regular languages. Internat. J. Found. Comput. Sci. 22, 1631–2653 (2011)
  0. 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)
  1. Hae-Sung Eom, Yo-Sub Han, Kai Salomaa: State complexity of k-union and k-intersection for prefix-free regular languages. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 26, 211–227 (2015)
  2. Juergen Dassow, Florin Manea, Bianca Truthe: Networks of evolutionary processors: the power of subregular filters. ACTA INFORMATICA 50, 41–75 (2013)
  3. Markus Holzer, Martin Kutrib, Katja Meckel: Nondeterministic state complexity of star-free languages. THEORETICAL COMPUTER SCIENCE 450, 68–80 (2012)
  4. Juergen Dassow, Florin Manea, Bianca Truthe: On external contextual grammars with subregular selection languages. THEORETICAL COMPUTER SCIENCE 449, 64–73 (2012)
  5. Arto Salomaa: Mirror images and schemes for the maximal complexity of nondeterminism. FUNDAMENTA INFORMATICAE 116, 237–249 (2012)
  6. Juergen Dassow, Florin Manea, Bianca Truthe: Networks of evolutionary processors with subregular filters. In: 5th International Conference on Language and Automata Theory and Applications, Tarragona, SPAIN, MAY 26-31, 2011. Lecture Notes in Computer Science, vol. 6638, pp. 262–273 (2011)
  7. Markus Holzer, Martin Kutrib, Katja Meckel: Nondeterministic state complexity of star-free languages. In: 16th International Conference on Implementation and Application of Automata (CIAA 2011), Univ Francois Rabelais Tours, Blois, FRANCE, JUL 13-16, 2011. Lecture Notes in Computer Science, vol. 6807, pp. 178–189 (2011)
• Galina Jirásková: Concatenation of regular languages and descriptional complexity. Theory Comput. Syst. 49, 301–218 (2011)
  0. 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)
  1. Markus Holzer, Sebastian Jakobi, Martin Kutrib: The magic number problem for subregular language families. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 115–131 (2012)
• 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)
  0. 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)
  1. Markus Holzer, Sebastian Jakobi, Martin Kutrib: The magic number problem for subregular language families. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 115–131 (2012)
• 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)
  1. Frederique Bassino, Laura Giambruno, Cyril Nicaud: Complexity of operations on cofinite languages. In: 9th Latin American Symposium on Theoretical Informatics (LATIN 2010), Benito Juarez Univ Oaxaca, Oaxaca City, MEXICO, APR 19-23, 2010. Lecture Notes in Computer Science, vol. 6034, pp. 222–233 (2010)
• Galina Jirásková: Deterministic blow-ups of minimal NFA's. RAIRO Theor. Inform. Appl. 40, 481–299 (2006)
  0. 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)
  1. Markus Holzer, Sebastian Jakobi, Martin Kutrib: The magic number problem for subregular language families. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 115–131 (2012)
  2. Markus Holzer, Martin Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 20, 563–580 (2009)
  3. Markus Holzer, Martin Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity. In: 13th International Conference on Implementation and Application of Automata, San Francisco State Univ, San Francisco, CA, JUL 21-24, 2008. LECTURE NOTES IN COMPUTER SCIENCE, vol. 5148, pp. 1–16 (2008)
  4. Villam Geffert: Magic numbers in the state hierarchy of finite automata. INFORMATION AND COMPUTATION 205, 1652–1670 (2007)
  5. Viliam Geffert: Magic numbers in the state hierarchy of finite automata. In: 31st International Symposium on Mathematical Foundations of Computer Science, Stara Lesna, SLOVAKIA, AUG 28-SEP 01, 2006. LECTURE NOTES IN COMPUTER SCIENCE, vol. 4162, pp. 412–423 (2006)
  6. L Van Zijl: Magic numbers for symmetric difference nfas. In: 6th International Workshop on Descriptional Complexity of Formal Systems, Univ Western Ontario, London, CANADA, JUL 26-28, 2004. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, vol. 16, pp. 1027–1038 (2005)
  7. K Iwama, A Matsuura, M Paterson: A family of nfas which need 2(n)-alpha deterministic states. In: 25th Conference on Mathematical Foundations of Computer Science, BRATISLAVA, SLOVAKIA, AUG 28-SEP 01, 2000. THEORETICAL COMPUTER SCIENCE, vol. 301, pp. 451–462 (2003)
• Jozef Jirásek, Galina Jirásková, Alexander Szabari: State complexity of concatenation and complementation. Internat. J. Found. Comput. Sci. 16, 511–229 (2005)
  0. 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)
  1. Hae-Sung Eom, Yo-Sub Han, Kai Salomaa: State complexity of k-union and k-intersection for prefix-free regular languages. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 26, 211–227 (2015)
  2. Hae-Sung Eom, Yo-Sub Han: State complexity of combined operations for suffix-free regular languages. THEORETICAL COMPUTER SCIENCE 510, 87–93 (2013)
  3. Yuan Gao, Lila Kari: State complexity of star of union and square of union on k regular languages. THEORETICAL COMPUTER SCIENCE 499, 38–50 (2013)
  4. Arto Salomaa, Kai Salomaa, Sheng Yu: Undecidability of state complexity. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 90, 1310–1320 (2013)
  5. Yuan Gao, Lila Kari, Sheng Yu: State complexity of union and intersection of square and reversal on k regular languages. THEORETICAL COMPUTER SCIENCE 454, 164–171 (2012)
  6. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of combined operations with two basic operations. THEORETICAL COMPUTER SCIENCE 437, 82–102 (2012)
  7. Yuan Gao, Lila Kari, Sheng Yu: State complexity of union and intersection of star on k regular languages. THEORETICAL COMPUTER SCIENCE 429, 98–107 (2012)
  8. Yuan Gao, Sheng Yu: State complexity of combined operations with union, intersection, star and reversal. FUNDAMENTA INFORMATICAE 116, 79–92 (2012)
  9. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of two combined operations: catenation-star and catenation-reversal. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 51–66 (2012)
  10. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of two combined operations: catenation-union and catenation-intersection. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 22, 1797–1812 (2011)
  11. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of catenation combined with union and intersection. In: 15th International Conference on Implementation and Application of Automata, Univ Manitoba, Winnipeg, CANADA, AUG 12-15, 2010. Lecture Notes in Computer Science, vol. 6482, pp. 95–104 (2011)
  12. Zoltan Esik, Yuan Gao, Guangwu Liu, Sheng Yu: Estimation of state complexity of combined operations. In: 10th International Workshop on Descriptional Complexity of Formal Systems, Charlottetown, CANADA, JUL 16-18, 2008. THEORETICAL COMPUTER SCIENCE, vol. 410, pp. 3272–3280 (2009)
  13. Markus Holzer, Martin Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 20, 563–580 (2009)
  14. Michael Domaratzki, Alexander Okhotin: State complexity of power. THEORETICAL COMPUTER SCIENCE 410, 2377–2392 (2009)
  15. Yo-Sub Han, Kai Salomaa, Derick Wood: Nondeterministic state complexity of basic operations for prefix-free regular languages. FUNDAMENTA INFORMATICAE 90, 93–106 (2009)
  16. Yo-Sub Han, Kai Salomaa: State complexity of basic operations on suffix-free regular languages. THEORETICAL COMPUTER SCIENCE 410, 2537–2548 (2009)
  17. Yo-Sub Han, Kai Salomaa: State complexity of union and intersection of finite languages. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 19, 581–595 (2008)
  18. Yuan Gao, Kai Salomaa, Sheng Yu: The state complexity of two combined operations: star of catenation and star of reversal. In: 8th International Workshop on Descriptional Complexity of Formal Systems, Las Cruces, NM, JUN 21-23, 2006. FUNDAMENTA INFORMATICAE, vol. 83, pp. 75–89 (2008)
  19. Markus Holzer, Martin Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity. In: 13th International Conference on Implementation and Application of Automata, San Francisco State Univ, San Francisco, CA, JUL 21-24, 2008. LECTURE NOTES IN COMPUTER SCIENCE, vol. 5148, pp. 1–16 (2008)
  20. Arto Salomaa, Kai Salomaa, Sheng Yu: State complexity of combined operations. In: Meeting of the American-Mathematical-Society, Santa Barbara, CA, 38443. THEORETICAL COMPUTER SCIENCE, vol. 383, pp. 140–152 (2007)
  21. Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Complementing two-way finite automata. In: 9th International Conference on Developments in Language Theory, Palermo, ITALY, JUL 04-08, 2005. INFORMATION AND COMPUTATION, vol. 205, pp. 1173–1187 (2007)
  22. Kai Salomaa, Sheng Yu: On the state complexity of combined operations and their estimation. In: 11th International Conference on Implementation and Application of Automata, Natl Taiwan Univ, Taipei, TAIWAN, AUG 21-23, 2006. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, vol. 18, pp. 683–698 (2007)
  23. Yo-Sub Han, Kai Salomaa: State complexity of union and intersection of finite languages. In: 11th International Conference on Developments in Language Theory, Univ Turku, Turku, FINLAND, JUL 03-06, 2007. LECTURE NOTES IN COMPUTER SCIENCE, vol. 4588, pp. 217–228 (2007)
  24. Yo-Sub Han, Kai Salomaa: State complexity of basic operations on suffix-free regular languages. In: 32nd International Symposium on Mathematical Foundations of Computer Science, Cesky Krumlov, CZECH REPUBLIC, AUG 26-31, 2007. LECTURE NOTES IN COMPUTER SCIENCE, vol. 4708, pp. 501–512 (2007)
  25. Sheng Yu: On the state complexity of combined operations. In: 11th International Conference on Implementation and Application of Automata, Natl Taiwan Univ, Taipei, TAIWAN, AUG 21-23, 2006. LECTURE NOTES IN COMPUTER SCIENCE, vol. 4094, pp. 11–22 (2006)
• Galina Jirásková: State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330, 281–298 (2005)
  0. 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)
  1. Alexander Okhotin, Kai Salomaa: Descriptional complexity of unambiguous input-driven pushdown automata. THEORETICAL COMPUTER SCIENCE 566, 1–11 (2015)
  2. Benny Kimelfeld, Christopher Re: Transducing markov sequences. JOURNAL OF THE ACM 61, – (2014)
  3. Pietro Baroni, Federico Cerutti, Paul E. Dunne, Massimiliano Giacomin: Automata for infinite argumentation structures. ARTIFICIAL INTELLIGENCE 203, 104–150 (2013)
  4. Yuan Gao, Lila Kari: State complexity of star of union and square of union on k regular languages. THEORETICAL COMPUTER SCIENCE 499, 38–50 (2013)
  5. Yuan Gao, Lila Kari, Sheng Yu: State complexity of union and intersection of square and reversal on k regular languages. THEORETICAL COMPUTER SCIENCE 454, 164–171 (2012)
  6. Markus Holzer, Martin Kutrib, Katja Meckel: Nondeterministic state complexity of star-free languages. THEORETICAL COMPUTER SCIENCE 450, 68–80 (2012)
  7. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of combined operations with two basic operations. THEORETICAL COMPUTER SCIENCE 437, 82–102 (2012)
  8. Yuan Gao, Lila Kari, Sheng Yu: State complexity of union and intersection of star on k regular languages. THEORETICAL COMPUTER SCIENCE 429, 98–107 (2012)
  9. Xiaoxue Piao, Kai Salomaa: State complexity of the concatenation of regular tree languages. THEORETICAL COMPUTER SCIENCE 429, 273–281 (2012)
  10. Christos Kapoutsis, Richard Kralovic, Tobias Moemke: Size complexity of rotating and sweeping automata. JOURNAL OF COMPUTER AND SYSTEM SCIENCES 78, 537–558 (2012)
  11. Yuan Gao, Sheng Yu: State complexity of combined operations with union, intersection, star and reversal. FUNDAMENTA INFORMATICAE 116, 79–92 (2012)
  12. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of two combined operations: catenation-star and catenation-reversal. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23, 51–66 (2012)
  13. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of two combined operations: catenation-union and catenation-intersection. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 22, 1797–1812 (2011)
  14. Elena Pribavkina, Emanuele Rodaro: State complexity of code operators. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 22, 1669–1681 (2011)
  15. Kai Salomaa: Limitations of lower bound methods for deterministic nested word automata. In: 3rd International Conference on Language and Automata Theory and Applications, Tarragona, SPAIN, APR 02-08, 2009. INFORMATION AND COMPUTATION, vol. 209, pp. 580–589 (2011)
  16. Alexander Okhotin, Kai Salomaa: Descriptional complexity of unambiguous nested word automata. In: 5th International Conference on Language and Automata Theory and Applications, Tarragona, SPAIN, MAY 26-31, 2011. Lecture Notes in Computer Science, vol. 6638, pp. 414–426 (2011)
  17. Markus Holzer, Martin Kutrib, Katja Meckel: Nondeterministic state complexity of star-free languages. In: 16th International Conference on Implementation and Application of Automata (CIAA 2011), Univ Francois Rabelais Tours, Blois, FRANCE, JUL 13-16, 2011. Lecture Notes in Computer Science, vol. 6807, pp. 178–189 (2011)
  18. Yuan Gao, Kai Salomaa, Sheng Yu: Transition complexity of incomplete dfas. FUNDAMENTA INFORMATICAE 110, 143–158 (2011)
  19. Bo Cui, Yuan Gao, Lila Kari, Sheng Yu: State complexity of catenation combined with union and intersection. In: 15th International Conference on Implementation and Application of Automata, Univ Manitoba, Winnipeg, CANADA, AUG 12-15, 2010. Lecture Notes in Computer Science, vol. 6482, pp. 95–104 (2011)
  20. Elena V. Pribavkina, Emanuele Rodaro: State complexity of prefix, suffix, bifix and infix operators on regular languages. In: 14th International Conference on Developments in Language Theory, Univ Western Ontario, London, CANADA, AUG 17-20, 2010. Lecture Notes in Computer Science, vol. 6224, pp. 376–386 (2010)
  21. Alexander Okhotin: On the state complexity of scattered substrings and superstrings. FUNDAMENTA INFORMATICAE 99, 325–338 (2010)
  22. Mark Daley, Michael Domaratzki, Kai Salomaa: Orthogonal concatenation: language equations and state complexity. JOURNAL OF UNIVERSAL COMPUTER SCIENCE 16, 653–675 (2010)
  23. Benny Kimelfeld, Christopher Re: Transducing markov sequences. In: 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Indianapolis, IN, JUN 06-11, 2010. PODS 2010: PROCEEDINGS OF THE TWENTY-NINTH ACM SIGMOD-SIGACT-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, vol. , pp. 15–26 (2010)
  24. Jui-Yi Kao, Narad Rampersad, Jeffrey Shallit: On nfas where all states are final, initial, or both. THEORETICAL COMPUTER SCIENCE 410, 5010–5021 (2009)
  25. Zoltan Esik, Yuan Gao, Guangwu Liu, Sheng Yu: Estimation of state complexity of combined operations. In: 10th International Workshop on Descriptional Complexity of Formal Systems, Charlottetown, CANADA, JUL 16-18, 2008. THEORETICAL COMPUTER SCIENCE, vol. 410, pp. 3272–3280 (2009)
  26. Yo-Sub Han, Kai Salomaa: Nondeterministic state complexity of nested word automata. THEORETICAL COMPUTER SCIENCE 410, 2961–2971 (2009)
  27. Markus Holzer, Martin Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 20, 563–580 (2009)
  28. Yo-Sub Han, Kai Salomaa, Derick Wood: Nondeterministic state complexity of basic operations for prefix-free regular languages. FUNDAMENTA INFORMATICAE 90, 93–106 (2009)
  29. Kai Salomaa: State complexity of nested word automata. In: 3rd International Conference on Language and Automata Theory and Applications, Tarragona, SPAIN, APR 02-08, 2009. Lecture Notes in Computer Science, vol. 5457, pp. 59–70 (2009)
  30. Martin Kutrib, Jens Reimann: Succinct description of regular languages by weak restarting automata. In: 1st International Conference on Language and Automata Theory and Applications, Tarragona, SPAIN, MAR 28-APR 02, 2007. INFORMATION AND COMPUTATION, vol. 206, pp. 1152–1160 (2008)
  31. Yuan Gao, Kai Salomaa, Sheng Yu: The state complexity of two combined operations: star of catenation and star of reversal. In: 8th International Workshop on Descriptional Complexity of Formal Systems, Las Cruces, NM, JUN 21-23, 2006. FUNDAMENTA INFORMATICAE, vol. 83, pp. 75–89 (2008)
  32. Markus Holzer, Martin Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity. In: 13th International Conference on Implementation and Application of Automata, San Francisco State Univ, San Francisco, CA, JUL 21-24, 2008. LECTURE NOTES IN COMPUTER SCIENCE, vol. 5148, pp. 1–16 (2008)
  33. QiQi Yan: Lower bounds for complementation of omega-automata via the full technique. In: 33rd International Colloquium on Automata, Languages and Programming, Venice, ITALY, JUL 10-14, 2006. LOGICAL METHODS IN COMPUTER SCIENCE, vol. 4, pp. – (2008)
  34. Michael Domaratzki, Kai Salomaa: Transition complexity of language operations. In: 8th International Workshop on Descriptional Complexity of Forman Systems, Las Cruces, NM, JUN 21-23, 2006. THEORETICAL COMPUTER SCIENCE, vol. 387, pp. 147–154 (2007)
  35. Arto Salomaa, Kai Salomaa, Sheng Yu: State complexity of combined operations. In: Meeting of the American-Mathematical-Society, Santa Barbara, CA, 38443. THEORETICAL COMPUTER SCIENCE, vol. 383, pp. 140–152 (2007)
  36. Kai Salomaa, Sheng Yu: On the state complexity of combined operations and their estimation. In: 11th International Conference on Implementation and Application of Automata, Natl Taiwan Univ, Taipei, TAIWAN, AUG 21-23, 2006. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, vol. 18, pp. 683–698 (2007)
  37. N Rampersad: The state complexity of l-2 and l-k. INFORMATION PROCESSING LETTERS 98, 231–234 (2006)
  38. Qiqi Yan: Lower bounds for complementation of omega-automata via the full automata technique. In: 33rd International Colloquium on Automata, Languages and Programming, Venice, ITALY, JUL 10-14, 2006. Lecture Notes in Computer Science, vol. 4052, pp. 589–600 (2006)
• Galina Kumičáková-Jirásková: Chomsky hierarchy and communication complexity. Elektronische Informationsverarbeitung und Kybernetik 25, 151–264 (1989)
  0. 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)
  1. J WACZULIK: Area time squared and area complexity of vlsi computations is strongly unclosed under union and intersection. LECTURE NOTES IN COMPUTER SCIENCE 464, 278–287 (1990)

<<<- back