Undecidability of state complexity

References

• Beesley , K. R. and Karttunen , L. 2003 . Finite State Morphology , Stanford , CA : CSLI Publications .
   Google Scholar
• Bouchou-Markhoff , B. , Caron , P. , Champarnaud , J.-M. and Maurel , D. Implementation and Application of Automata – 16th International Conference . Edited by: Bouchou-Markhoff , B. , Caron , P. , Champarnaud , J.-M. and Maurel , D. CIAA’11, Blois, France, July 12–16, 2011, LNCS Vol. 6807, Springer, y2011.
   Google Scholar
• Campeanu , C. , Culik , K. , Salomaa , K. and Yu , S. State complexity of basic operations on finite language . Proceedings of the Fourth International Workshop on Implementing Automata . July 17–19 1999 , Potsdam , Germany. pp. 60 – 70 . Springer . LNCS Vol. 2214
   Google Scholar
• Campeanu , C. , Salomaa , K. and Yu , S. 2002 . Tight lower bound for the state complexity of shuffle of regular languages . J. Autom. Lang. Comb. , 7 ( 3 ) : 303 – 310 .
   Google Scholar
• Cui , B. , Gao , Y. , Kari , L. and Yu , S. State complexity of catenation combined with union and intersection . Proceedings of CIAA 2010 . Winnipeg .
   Google Scholar
• Cui , B. , Gao , Y. , Kari , L. and Yu , S. 2012 . State complexity of combined operations with two basic operations . Theor. Comput. Sci. , 437 : 82 – 102 . (doi:10.1016/j.tcs.2012.02.030)
   Web of Science ®Google Scholar
• Domaratzki , M. 2002 . State complexity and proportional removals . J. Autom. Lang. Comb. , 7 : 455 – 468 .
   Google Scholar
• Domaratzki , M. and Okhotin , A. 2009 . State complexity of power . Theoret. Comput. Sci. , 410 ( 24–25 ) : 2377 – 2392 . (doi:10.1016/j.tcs.2009.02.025)
   Web of Science ®Google Scholar
• Ésik , Z. , Gao , Y. , Liu , G. and Yu , S. 2009 . Estimation of state complexity of combined operations . Theoret. Comput. Sci. , 410 ( 35 ) : 3272 – 3280 . (doi:10.1016/j.tcs.2009.03.026)
   Web of Science ®Google Scholar
• Gao , Y. and Yu , S. 2009 . State complexity approximation . Electronic Proc. Theoret. Comput. Sci. , 3 : 121 – 130 . (doi:10.4204/EPTCS.3.11)
   Google Scholar
• Gao , Y. and Yu , S. State complexity of four combined operations composed of union, intersection, star and reversal . Proceedings of DCFS’11 . July 25–27 2011 , Giessen/Limburg , Germany. pp. 158 – 171 . Springer . LNCS Vol. 6808
   Google Scholar
• Gao , Y. , Salomaa , K. and Yu , S. 2008 . The state complexity of two combined operations: Star of catenation and star of reversal . Fund. Inform. , 83 ( 1–2 ) : 75 – 89 .
   Web of Science ®Google Scholar
• Holzer , M. and Kutrib , M. 2003 . Nondeterministic descriptional complexity of regular languages . Int. J. Found. Comput. Sci. , 14 : 1087 – 1102 . (doi:10.1142/S0129054103002199)
   Google Scholar
• Holzer , M. and Kutrib , M. 2011 . Descriptional and computational complexity of finite automata – a survey . Inform. Comput. , 209 : 456 – 470 . (doi:10.1016/j.ic.2010.11.013)
   Web of Science ®Google Scholar
• Jirásková , G. 2005 . State complexity of some operations on binary regular languages . Theoret. Comput. Sci. , 330 : 287 – 298 . (doi:10.1016/j.tcs.2004.04.011)
   Web of Science ®Google Scholar
• Jirásková , G. and Okhotin , A. State complexity of cyclic shift . Proceedings of Descriptional Complexity of Formal Systems . Como , Italy. pp. 182 – 193 .
   Google Scholar
• Jirásková , G. and Okhotin , A. 2011 . On the state complexity of star of union and star of intersection . Fundam. Inform. , 109 : 161 – 178 .
   Web of Science ®Google Scholar
• Jirásek , J. , Jirásková , G. and Szabari , A. 2005 . State complexity of concatenation and complementation of regular languages . Int. J. Found. Comput. Sci. , 16 : 511 – 529 . (doi:10.1142/S0129054105003133)
   Web of Science ®Google Scholar
• Kiraz , G. A. Compressed storage of sparse finite-state transducers . Proceedings of 4th International Workshop on Implementing Automata (WIA 1999) . July 17–19 1999 , Potsdam , Germany. pp. 109 – 121 . Springer . LNCS Vol. 2214
   Google Scholar
• Liu , G. , Martin-Vide , C. , Salomaa , A. and Yu , S. 2008 . State complexity of basic language operations combined with reversal . Inform. Comput. , 206 : 1178 – 1186 . (doi:10.1016/j.ic.2008.03.018)
   Web of Science ®Google Scholar
• Lupanov , O. B. 1963 . A comparison of two types of finite automata . Russian, Problemy Kibernitiki , 9 : 321 – 326 .
   Google Scholar
• Pighizzini , G. and Shallit , J. O. 2002 . Unary language operations, state complexity and Jacobsthal's function . Int. J. Found. Comput. Sci. , 13 : 145 – 159 . (doi:10.1142/S012905410200100X)
   Google Scholar
• Rabin , M. and Scott , D. 1959 . Finite automata and their decision problems . IBM J. Res. Dev. , 3 ( 2 ) : 114 – 125 . (doi:10.1147/rd.32.0114)
   Web of Science ®Google Scholar
• Rampersad , N. 2006 . The state complexity of L2 and Lk . Inform. Process. Lett. , 98 ( 2 ) : 231 – 234 . (doi:10.1016/j.ipl.2005.06.011)
   Web of Science ®Google Scholar
• Rozenberg , G. and Salomaa , A. 1994 . Cornerstones of Undecidability , New York, London : Prentice Hall .
   Google Scholar
• Rozenberg , G. and Salomaa , A. 1997 . Handbook of Formal Languages 1–3 , Edited by: Rozenberg , G. and Salomaa , A. Berlin, Heidelberg, New York : Springer-Verlag .
   Google Scholar
• Salomaa , A. 2012 . “ Undecidability of state complexities using mirror images ” . to appear
   Google Scholar
• Salomaa , K. and Yu , S. 2007 . On the state complexity of combined operations and their estimation . Int. J. Found. Comput. Sci. , 18 ( 4 ) : 683 – 698 . (doi:10.1142/S0129054107004917)
   Web of Science ®Google Scholar
• Salomaa , A. , Wood , D. and Yu , S. 2004 . On the state complexity of reversals of regular languages . Theoret. Comput. Sci. , 320 : 293 – 313 . (doi:10.1016/j.tcs.2004.02.032)
   Web of Science ®Google Scholar
• Salomaa , A. , Salomaa , K. and Yu , S. 2007 . State complexity of combined operations . Theoret. Comput. Sci. , 383 : 140 – 152 . (doi:10.1016/j.tcs.2007.04.015)
   Web of Science ®Google Scholar
• Shallit , J. 2009 . A Second Course in Formal Languages and Automata Theory , New York, NY : Cambridge University Press .
   Google Scholar
• Yu , S. On the state complexity of combined operations . International Conference on Implementation and Application of Automata (CIAA 2006), invited lecture . August 21–23 2006 , Taipei , Taiwan. pp. 11 – 22 . Springer . LNCS Vol. 4094
   Google Scholar
• Yu , S. and Gao , Y. State complexity research and approximation . 15th International Conference on Developments in Language Theory (DLT 2011), invited talk . July 19–22 2011 , Milan , Italy. pp. 46 – 57 . Springer . LNCS Vol. 6795
   Google Scholar
• Yu , S. , Zhuang , Q. and Salomaa , K. 1994 . The state complexities of some basic operations on regular languages . Theoret. Comput. Sci. , 125 : 315 – 328 . (doi:10.1016/0304-3975(92)00011-F)
   Web of Science ®Google Scholar