Kai Salomaa: Publications 2005-2009

• Y.-S. Han, K. Salomaa: Nondeterministic state complexity of nested word automata. Theoretical Computer Science, Vol. 410, No. 30-32, (2009) 2961-2971.
• K. Salomaa, S. Yu, J. Zan: Deciding determinism of caterpillar expressions. Theoretical Computer Science, Vol. 410, No. 37, (2009) 3438-3446.
• A. Salomaa, K. Salomaa, S. Yu: Variants of codes and indecomposable languages. Information and Computation, Vol. 207, No. 11, (2009) 1340-1349.
• X. Piao, K. Salomaa: Operational state complexity of nested word automata. Theoretical Computer Science, Vol. 410, No. 35, (2009) 3290-3302.
• F. Biegler, K. Salomaa: On the synchronized derivation depth of context-free grammars. Theoretical Computer Science, Vol. 410, No. 35, (2009) 3198-3208.
• E. Czeizler, E. Czeizler, L. Kari, K. Salomaa: On the descriptional complexity of Watson-Crick automata. Theoretical Computer Science, Vol. 410, No. 35, (2009) 3250-3260.
• Y.-S. Han, K. Salomaa, D. Wood: Nondeterministic state complexity of basic operations for prefix-free regular languages. Fundamenta Informaticae, Vol. 90 (2009) 93-106.
• Y.-S. Han, K. Salomaa: State complexity of basic operations on suffix-free regular languages. Theoretical Computer Science, Vol. 410, No. 27--29, (2009) 2537-2548.
• A. Clarridge, K. Salomaa: A cellular automaton model for car traffic with a slow-to-stop rule, Proceedings of the 14th International Conference on Implementation and Application of Automata, CIAA'09, Springer Lect. Notes Comput. Sci. 5642, Springer, 2009, pp. 44-53.
• A. Clarridge, K. Salomaa: A crypto-system based on the composition of reversible cellular automata, Proceedings of 3rd International Conference Language and Automata Theory and Applications, LATA'09, Lect. Notes Comput. Sci. 5457, Springer, 2009, pp. 314-315. Preliminary version: Queen's School of Computing TR 2008-549
• Y.-S. Han, K. Salomaa, S. Yu: State complexity of combined operations for prefix-free regular languages. Proceedings of 3rd International Conference Language and Automata Theory and Applications, LATA'09, Lect. Notes Comput. Sci. 5457, Springer, 2009, pp. 398-409.
• K. Salomaa: State complexity of nested word automata. Proceedings of 3rd International Conference Language and Automata Theory and Applications, LATA'09, Lect. Notes Comput. Sci., Vol. 5457, Springer-Verlag, 2009, pp. 59--70.
• Y.-S. Han, K. Salomaa, D. Wood: Operational state complexity of prefix-free regular languages. In: Z. \'{E}sik, Z. F\"ul\"op (Eds.) Automata, Formal Languages and Related Topics, Institute of Informatics, University of Szeged, 2009, pp. 99-115.
• X. Piao, K. Salomaa: Operational state complexity of nested word automata. Proceedings of the 10th Workshop Descriptional Complexity of Formal Systems, DCFS 2008, (C. Campeanu, G. Pighizzini, Eds.), 2008, pp. 194-206.
• M. Domaratzki, K. Salomaa: Lower bounds for the transition complexity of NFAs. Journal of Computer and System Sciences, Vol. 74 (2008) 1116-1130. DOI: 10.1016/j.jcss.2008.02.007 , Preliminary TR version.
• Y.-S. Han, K. Salomaa: State complexity of union and intersection of finite languages. International Journal of Foundations of Computer Science, Vol. 19 (2008) 581-595.
• Y. Gao, K. Salomaa, S. Yu: The state complexity of two combined operations: star of catenation and star of reversal. Fundamenta Informaticae, Vol. 83 (2008) 75-89.
• K. Salomaa: Language decompositions, primality, and trajectory-based operations. Proceedings of 13th International Conference Implementation and Application of Automata, CIAA 2008, Lect. Notes Comput. Sci., Vol. 5148, Springer-Verlag, 2008, pp. 17-22.
• F. Biegler, K. Salomaa: On the synchronized derivation depth of context-free grammars. Proceedings of the 10th Workshop Descriptional Complexity of Formal Systems, DCFS 2008, (C. Campeanu, G. Pighizzini, Eds.), 2008, pp. 73-84.
• E. Czeizler, E. Czeizler, L. Kari, K. Salomaa: Watson-Crick automata: Determinism and state complexity. Proceedings of the 10th Workshop Descriptional Complexity of Formal Systems, DCFS 2008, (C. C\^ampeanu, G. Pighizzini, Eds.), 2008, pp. 121-133.
• M. Daley, M. Domaratzki, K. Salomaa: State complexity of orthogonal catenation. Proceedings of the 10th Workshop Descriptional Complexity of Formal Systems, DCFS 2008, (C. C\^ampeanu, G. Pighizzini, Eds.), 2008, pp. 134-144.
• A. Salomaa, K. Salomaa, S. Yu: Length codes, products of languages and primality. Proceedings of 2nd International Conference Language and Automata Theory and Applications, LATA'08, Lect. Notes Comput. Sci. Vol. 5196, Springer, 2008, pp.476-486.
• M. Domaratzki, K. Salomaa: Transition complexity of language operations. Theoretical Computer Science, Vol. 387 (2007) 147-154.
• B. Cordy, K. Salomaa: On the existence of regular approximations. Theoretical Computer Science, Vol. 387 (2007) 125-135.
• K. Salomaa, P. Schofield: State complexity of additive weighted finite automata, International Journal of Foundations of Computer Science, Vol. 18 (2007) 1407-1416.
• F. Biegler, I. McQuillan, K. Salomaa: An infinite hierarchy induced by depth synchronization. Theoretical Computer Science, Vol. 387 (2007) 113-124.
• Y.-S. Han, A. Salomaa, K. Salomaa, D. Wood, S. Yu: On the existence of prime decompositions. Theoretical Computer Science, Vol. 376 (2007) 60-69.
• K. Salomaa, S. Yu: On the state complexity of combined operations and their estimation. International Journal of Foundations of Computer Science, Vol. 18 (2007) 683-698.
• A. Salomaa, K. Salomaa, S. Yu: State complexity of combined operations. Theoretical Computer Science, Vol. 383 (2007) 140-152.
• Y.-S. Han, K. Salomaa, D. Wood: Intercode regular languages, Fundamenta Informaticae, Vol. 76 (2007) 113-128.
• Y.-S. Han, K. Salomaa: State complexity of basic operations on suffix-free regular languages. Proceedings of 32nd International Symposium Mathematical Foundations of Computer Science, MFCS'07, Lect. Notes Comput. Sci. Vol. 4708, Springer, 2007, pp. 501 - 512. TR version.
• K. Salomaa, S. Yu, J. Zan: Deterministic caterpillar expressions. Proceedings of the 12th International Conference Implementation and Application of Automata, CIAA 2007, Lect. Notes Comput. Sci., Vol. 4793, Springer-Verlag, 2007, pp. 97 - 108. TR version.
• Y.-S. Han, K. Salomaa: State complexity of union and intersection of finite languages. Proceedings of 11th International Conference Developments in Language Theory, DLT 2007, Lect. Notes Comput. Sci., Vol. 4588, Springer-Verlag, 2007, pp. 217 - 228.
• K. Salomaa: Descriptional complexity of nondeterministic finite automata. Proceedings of 11th International Conference Developments in Language Theory, DLT 2007, Lect. Notes Comput. Sci., Vol. 4588, Springer-Verlag, 2007, pp. 31 - 35.
• M. Daley, M. Domaratzki, K. Salomaa: Orthogonality of language operations. Proceedings of Theory and Applications of Language Equations, TALE 2007, M. Kunc, A. Okhotin (Eds.), TUCS General Publication No. 44, June 2007, pp. 43 - 53.
• M. Domaratzki, K. Salomaa: Codes defined by multiple sets of trajectories. Theoretical Computer Science, Vol. 366 (2006) 182 - 193.
• M. Domaratzki, G. Rozenberg, K. Salomaa: Interpreted trajectories. Fundamenta Informaticae Vol. 73 (2006) 81 - 97.
• Y.-S. Han, K. Salomaa, D. Wood: Prime decompositions of regular languages. Proceedings of DLT 2006, (O.H. Ibarra and Z. Dang, Eds.), Lecture Notes in Computer Science 4036, Springer, 2006, pp. 145 - 155. TR version.
• I. McQuillan, K. Salomaa, M. Daley: Iterated TGR languages: Membership problem and effective closure properties. Proceedings of 12th International Conference Computing and Combinatorics, COCOON 2006, Lect. Notes Comput. Sci., Vol. 4112, Springer-Verlag, 2006, pp. 94 - 103.
• M. Domaratzki, K. Salomaa: Lower bounds for the transition complexity of NFAs. Proceedings of 31st International Symposium Mathematical Foundations of Computer Science, MFCS 2006, Lect. Notes Comput. Sci., Vol. 4162, Springer-Verlag, 2006, pp. 315 - 326.
• Y.-S. Han, K. Salomaa, D. Wood: Prime decomposition of regular languages. Proceedings of 10th International Conference Developments in Language Theory, DLT 2006, Lect. Notes Comput. Sci., Vol. 4036, Springer-Verlag, 2006, pp. 145 - 155.
• F. Biegler, I. McQuillan, K. Salomaa: An infinite hierarchy induced by depth synchronization. Proceedings of 8th International Workshop DCFS'06, H. Leung, G. Pighizzini (Eds.), Las Cruces, NM, June 21 - 23, 2006, pp. 82 - 93.
• B. Cordy, K. Salomaa: Regular approximations of non-regular languages. Proceedings of 8th International Workshop DCFS'06, H. Leung, G. Pighizzini (Eds.), Las Cruces, NM, June 21 - 23, 2006, pp. 118 - 129.
• M. Domaratzki, K. Salomaa: Transition complexity of language operations. Proceedings of 8th International Workshop DCFS'06, H. Leung, G. Pighizzini (Eds.), Las Cruces, NM, June 21 - 23, 2006, pp. 141 - 152.
• Y. Gao, K. Salomaa, S. Yu: State complexity of star of catenation and reversal. Proceedings of 8th International Workshop DCFS'06, H. Leung, G. Pighizzini (Eds.), Las Cruces, NM, June 21 - 23, 2006, pp. 153 - 164.
• Y.-S. Han, K. Salomaa, D. Wood: State complexity of prefix-free regular languages. Proceedings of 8th International Workshop DCFS'06, H. Leung, G. Pighizzini (Eds.), Las Cruces, NM, June 21 - 23, 2006, pp. 165 - 176.
• M. Domaratzki, K. Salomaa: Decidability of trajectory-based equations. Theoretical Computer Science 345 (2005) 304 - 330.
• A. Okhotin, K. Salomaa: Contextual grammars with uniform sets of trajectories. Fundamenta Informaticae 64 (2005) 341 - 351.
• M. Domaratzki, K. Salomaa: Restricted sets of trajectories and decidability of shuffle decompositions. International Journal of Foundations of Computer Science 16 (2005) 897 - 912.
• M. Domaratzki, K. Salomaa: Codes defined by multiple sets of trajectories. Proc. of 11th International Conference Automata and Formal Languages, AFL 2005, Z. Esik, Z. Fulop (Eds.), Dobogoko, Hungary, May 17-20, 2005, pp. 97 - 111.