Decidability and Shortest Strings in Formal Languages

1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)

   MATH  Google Scholar 

2. Alpoge, L.: Post correspondence problem variant. Posted to (January 12, 2011), http://cstheory.stackexchange.com/questions/4284/post-correspondence-problem-variant

3. Ang, T.: Problems related to shortest strings in formal languages. M. Math. thesis. University of Waterloo (2010)

   Google Scholar 

4. Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. System Sci. 8, 315–332 (1974)

   Article  MATH  MathSciNet  Google Scholar 

5. Ellul, K., Krawetz, B., Shallit, J., Wang, M.-W.: Regular expressions: new results and open problems. J. Autom. Lang. Combin. 10, 407–437 (2005)

   MATH  Google Scholar 

6. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)

   MATH  Google Scholar 

7. Pighizzini, G., Shallit, J.: Unary language operations, state complexity, and Jacobsthal’s function. Int. J. Found. Comput. Sci. 13, 145–159 (2002)

   Article  MATH  MathSciNet  Google Scholar 

Download references