Special Issue – Developments in Language Theory (DLT 2011)No Access

STATE COMPLEXITY AND APPROXIMATION

YUAN GAO

Department of Computer Science, University of Western Ontario, London, Ontario, Canada

Search for more papers by this author

and

SHENG YU

Department of Computer Science, University of Western Ontario, London, Ontario, Canada

Search for more papers by this author

https://doi.org/10.1142/S0129054112400461Cited by:3 (Source: Crossref)

Abstract

We discuss a number of essential questions concerning the state complexity research. The questions include why many basic problems were not studied earlier, whether there is a general algorithm for state complexity of combined operations, and whether there is a new and effective approach in this area of research. The concept of state complexity approximation is also discussed. We show that state complexity approximation can be used to obtain good results when the exact state complexities are difficult to find and when the exact state complexities are too complex to comprehend. We also list a number of questions for future research in this area.

This work was partially supported by Natural Science and Engineering Research Council of Canada Discovery Grant 41630.

Keywords:

References

M. Almeida, N. Moreira and R. Reis, Theoretical Computer Science 387(2), 93 (2007), DOI: 10.1016/j.tcs.2007.07.029. Crossref, Web of Science, Google Scholar
T. H. Cormen , C. E. Leiserson and R. L. Rivest , Introduction to algorithms ( The MIT Press and McGraw-Hill , Massachusetts , 1990 ) . Google Scholar
B. Cuiet al., International Journal of Foundations of Computer Science 22(8), 1797 (2011), DOI: 10.1142/S0129054111009045. Link, Web of Science, Google Scholar
M. Domaratzki and K. Salomaa, Theoretical Computer Science 387(2), 147 (2007), DOI: 10.1016/j.tcs.2007.07.034. Crossref, Web of Science, Google Scholar
M. Domaratzki and K. Salomaa, Journal of Computer and System Sciences 74(7), 1116 (2008), DOI: 10.1016/j.jcss.2008.02.007. Crossref, Web of Science, Google Scholar
K. Ellul, Descriptional complexity measures of regular languages, Master's Thesis, University of Waterloo (Ontario, 2002) . Google Scholar
Z. Ésiket al., Theoretical Computer Science 410(35), 3272 (2009). Crossref, Web of Science, Google Scholar
S. Fujiwaraet al., IEEE Transactions on Software Engineering 17, 591 (1991), DOI: 10.1109/32.87284. Crossref, Web of Science, Google Scholar
Y. Gao, K. Salomaa and S. Yu, Fundamenta Informaticae 83(2), 75 (2008). Web of Science, Google Scholar
Y. Gao and S. Yu, State complexity approximation, Proceedings of Descriptional Complexity of Formal Systems (2009) pp. 163–174. Google Scholar
M. R. Garey, R. L. Graham and J. D. Ullman, Worst-case analysis of memory allocation algorithms, Proceedings of the 4th Annual ACM Symposium on the Theory of Computing (1972) pp. 143–150. Google Scholar
H. Gruber and M. Holzer, Theoretical Computer Science 387(2), 155 (2007), DOI: 10.1016/j.tcs.2007.07.035. Crossref, Web of Science, Google Scholar
M. Holzer and M. Kutrib, International Journal of Foundations Computer Science 14, 1087 (2003), DOI: 10.1142/S0129054103002199. Link, Google Scholar
M. Holzer and M. Kutrib, Unary language operations and their nondeterministic state complexity, Developments in Language Theory, 6th International Conference2450, Lecture Notes in Computer Science (Springer, 2003) pp. 162–172. Google Scholar
J.E. Hopcroft and J.D. Ullman, Introduction to automata theory, languages, and computation, Addison Wesley, (Reading, Massachusetts, 1979) . Google Scholar
D. S. Johnson, Fast allocation algorithms, Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory (1972) pp. 144–154. Google Scholar
D.S. Johnson, Near-optimal bin packing algorithms, PhD Dissertation, Massachusetts Institute of Technology, Cambridge, MA, 1993 . Google Scholar
G. A. Kiraz, Compressed Storage of Sparse Finite-State Transducers, Proceedings of CIAA 20012214, LNCS (Springer, 2001) pp. 109–121. Google Scholar
L. Karttunen, Private communication . Google Scholar
O. B. Lupanov, Problemy Kibernetiki 9, 321 (1963). Google Scholar
A.N. Maslov, "Estimates of the number of states of finite automata", Dokl. Akad. Nauk SSSR 194 (1970) 1266-1268 (in Russian). English translation: Soviet Math. Dokl. 11 (1970) 1372–1375 . Google Scholar
A. R. Meyer and M. J. Fischer, Economy of Description by Automata, Grammars, and Formal Systems, 12th IEEE Symposium on Switching and Automata Theory (1971) pp. 188–191. Google Scholar
F. Moore, IEEE Trans. Comput. C 20, 1211 (1971). Web of Science, Google Scholar
G. Rozenberg and A. Salomaa , Cornerstones of Undecidability ( Prentice Hall , New York, London , 1994 ) . Google Scholar
J. Rumbaugh , I. Jacobson and G. Booch , The United Modeling Language Reference Manual ( Addison-Wesley , 1999 ) . Google Scholar
A. Salomaa , Theory of automata ( Pergamon Press , Oxford , 1969 ) . Google Scholar
A. Salomaa , K. Salomaa and S. Yu , Undecidability of the state complexity of composed regular operations , Proceedings of LATA 2011 ( 2011 ) . Google Scholar
K. Salomaa and S. Yu, Theoretical Computer Science 207, 73 (1998), DOI: 10.1016/S0304-3975(98)00056-5. Crossref, Web of Science, Google Scholar
A. Salomaa, K. Salomaa and S. Yu, Theoretical Computer Science 383(3), 140 (2007), DOI: 10.1016/j.tcs.2007.04.015. Crossref, Web of Science, Google Scholar
K. Salomaa and S. Yu, International Journal of Foundations of Computer Science 18(4), 683 (2007), DOI: 10.1142/S0129054107004917. Link, Web of Science, Google Scholar
S. Watt, Private communication . Google Scholar
S. Yu, Handbook of formal languages 1, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, New York, 1997) pp. 41–110. Crossref, Google Scholar
S. Yu, Q. Zhuang and K. Salomaa, Theoretical Computer Science 125(2), 315 (1994), DOI: 10.1016/0304-3975(92)00011-F. Crossref, Web of Science, Google Scholar