References

  1. Janusz A. Brzozowski (2013): In Search of Most Complex Regular Languages. Intern. J. of Foundations of Comp. Sc. 24(6), pp. 691–708. Available at http://dx.doi.org/10.1142/S0129054113400133.
  2. Janusz A. Brzozowski, Galina Jirásková, Bo Liu, Aayush Rajasekaran & Marek Szykula (2016): On the State Complexity of the Shuffle of Regular Languages. In: Descriptional Complexity of Formal Systems - 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings, pp. 73–86, doi:10.1007/978-3-319-41114-9_6.
  3. Pascal Caron, Edwin Hamel-De le court, Jean-Gabriel Luque & Bruno Patrou (2018): New tools for state complexity. CoRR abs/1807.00663. Available at http://arxiv.org/abs/1807.00663.
  4. Pascal Caron, Jean-Gabriel Luque, Ludovic Mignot & Bruno Patrou (2016): State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach. Int. J. Found. Comput. Sci. 27(6), pp. 675–704, doi:10.1142/S0129054116500234.
  5. Pascal Caron, Jean-Gabriel Luque & Bruno Patrou (2016): State complexity of multiple catenation. CoRR abs/1607.04031. Available at http://arxiv.org/abs/1607.04031.
  6. Pascal Caron, Jean-Gabriel Luque & Bruno Patrou (2017): State complexity of catenation combined with boolean operations. CoRR abs/1707.03174. Available at http://arxiv.org/abs/1707.03174.
  7. Bo Cui, Yuan Gao, Lila Kari & Sheng Yu (2011): State Complexity of Two Combined Operations: Catenation-Union and Catenation-Intersection. Int. J. Found. Comput. Sci. 22(8), pp. 1797–1812. Available at http://dx.doi.org/10.1142/S0129054111009045.
  8. Sylvie Davies (2018): A General Approach to State Complexity of Operations: Formalization and Limitations. Developments in Language Theory, doi:10.1007/978-3-319-98654-8_21.
  9. Michael Domaratzki (2002): State Complexity of Proportional Removals. Journal of Automata, Languages and Combinatorics 7(4), pp. 455–468, doi:10.25596/jalc-2002-455.
  10. Michael Domaratzki & Alexander Okhotin (2009): State complexity of power. Theoretical Computer Science 410(24), pp. 2377 – 2392, doi:10.1016/j.tcs.2009.02.025. Available at http://www.sciencedirect.com/science/article/pii/S0304397509001820. Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu.
  11. Yuan Gao, Nelma Moreira, Rogério Reis & Sheng Yu (2017): A Survey on Operational State Complexity. Journal of Automata, Languages and Combinatorics 21(4), pp. 251–310, doi:10.25596/jalc-2016-251.
  12. Yuan Gao, Kai Salomaa & Sheng Yu (2008): The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal. Fundam. Inf. 83(1-2), pp. 75–89. Available at http://dl.acm.org/citation.cfm?id=1377804.1377812.
  13. J. E. Hopcroft & J. D. Ullman (1979): Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.
  14. Jozef Jirásek, Galina Jirásková & Alexander Szabari (2005): State complexity of concatenation and complementation. Int. J. Found. Comput. Sci. 16(3), pp. 511–529. Available at http://dx.doi.org/10.1142/S0129054105003133.
  15. Galina Jirásková (2005): State complexity of some operations on binary regular languages. Theor. Comput. Sci. 330(2), pp. 287–298. Available at http://dx.doi.org/10.1016/j.tcs.2004.04.011.
  16. Galina Jirásková & Alexander Okhotin (2008): State complexity of cyclic shift. ITA 42(2), pp. 335–360, doi:10.1051/ita:2007038.
  17. Galina Jirásková & Alexander Okhotin (2011): On the State Complexity of Star of Union and Star of Intersection. Fundam. Inform. 109(2), pp. 161–178. Available at http://dx.doi.org/10.3233/FI-2011-502.
  18. Arto Salomaa, Kai Salomaa & Sheng Yu (2007): State complexity of combined operations. Theor. Comput. Sci. 383(2-3), pp. 140–152. Available at http://dx.doi.org/10.1016/j.tcs.2007.04.015.
  19. Sheng Yu (2001): State Complexity of Regular Languages. Journal of Automata, Languages and Combinatorics 6(2), pp. 221, doi:10.25596/jalc-2001-221.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org