Transition Complexity of Incomplete DFAs

• Autorzy: Gao Y. , Salomaa K. , Yu S
• Języki publikacji: EN

Abstrakty

EN

We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.

Słowa kluczowe

EN

transition complexity; deterministic finite automaton; incomplete automaton; regular language; Boolean operations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 143--158
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Gao Y.

autor

Salomaa K.

autor

Yu S

• Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7,

Bibliografia

• [1] K.R. Beesley, L. Karttunen: Finite state morphology, CSLI Studies in Computational Linguistics, 2003
• [2] C. G. Cassandras, S. Lafortune: Introduction to discrete event systems, Springer-Verlag, 2006
• [3] M. Chrobak: Finite automata and unary languages, Theoretical Computer Science 47(2) (1986) 149-158
• [4] B. Cui, Y. Gao, L. Kari, S. Yu: State complexity of catenation combined with union and intersection, Proc. 15th Internat. Conference Implementation and Application of Automata, CIAA, LNCS 6482 (2011) 95-104
• [5] M. Domaratzki, K. Salomaa: Transition complexity of language operations, Theoretical Computer Science 387(2) (2007) 147-154
• [6] M. Domaratzki, K. Salomaa: Lower bounds for the transition complexity of NFAs, Journal of Computer and System Sciences 74(7) (2008) 1116-1130
• [7] M. Domaratzki, A. Okhotin: State complexity of power, Theoretical Computer Science 410(24-25) (2009) 2377-2392
• [8] Y. Gao, K. Salomaa, S. Yu: Transition complexity of incomplete DFA's. Proc. 12th Workshop Descriptional Complexity of Formal Systems, DCFS 2010, (I. McQuillan, G. Pighizzini, B. Trost, Eds.), University of Saskatchewan, Tech. Report 2010-02, pp. 123-134.
• [9] H. Gruber, M. Holzer: On the average state and transition complexity of finite languages, Theoretical Computer Science 387(2) (2007) 155-166
• [10] M. Holzer, M. Kutrib: Nondeterministic finite automata - recent results on the descriptional and computational complexity, International Journal of Foundations of Computer Science 20(4) (2009) 563-580
• [11] G. Jirásková: State complexity of some operations on binary regular languages, Theoretical Computer Science 330(2) (2005) 287-298
• [12] A. Paun, M. Paun: State and transition complexity of Watson-Crick finite automata, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, LNCS 1684 (1999) 409-420
• [13] G. Pighizzini, J. Shallit: Unary language operations, state complexity and Jacobsthal's function, International Journal of Foundations of Computer Science 13(1) (2002) 145-159
• [14] K. Rudie: A summary of some discrete-event system control problems, Proc. 15th International Conference on Implementation and Application of Automata, CIAA'10, LNCS 6482 (2011) 4-16
• [15] A. Salomaa, K. Salomaa, S. Yu: State complexity of combined operations, Theoretical Computer Science 383(2-3) (2007) 140-152
• [16] J. Shallit: A second course in formal languages and automata theory, Cambridge University Press, 2009
• [17] S. Watt: Private communication
• [18] D. Wood: Theory of computation, John Wiley & Sons, 1987
• [19] S. Yu: State complexity of regular languages, Journal of Automata, Languages and Combinatorics 6(2) (2001) 221-234
• [20] S. Yu, Q. Zhuang, K. Salomaa: The state complexity of some basic operations on regular languages, Theoretical Computer Science 125(2) (1994) 315-328
• [21] S. Yu: Regular languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of formal languages, Vol. 1, Springer-Verlag, 1997, 41-110