Kai Salomaa: Publications since 2010

• A. Okhotin, K. Salomaa: Descriptional complexity of unambiguous input-driven pushdown automata. Submitted to Theoretical Computer Science.
• S. Choudhury, K. Salomaa, S.G. Akl, Cellular automaton based algorithms for the dispersion of mobile wireless sensor networks, 25 pp. Submitted to International Journal of Parallel, Emergent and Distributed Systems, September 2012.
• A. Palioudakis, K. Salomaa, S.G. Akl, State complexity of finite tree width NFAs. Submitted to Journal of Automata, Languages and Combinatorics.
• H.-S. Eom, Y.-S. Han, K. Salomaa, S. Yu: State complexity of combined operations for prefix-free regular languages, 14 pp. Submitted to Fundamenta Informaticae.
• X. Piao, K. Salomaa: Lower bounds for the size of deterministic unranked tree automata. Theoretical Computer Science, Vol. 454 (2012) 231--239. doi:10.1016/j.tcs.2012.03.043
• D. Sears, K. Salomaa: Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes. Natural Computing, accepted for publication (April 2012)
• S. Choudhury, K. Salomaa, S.G. Akl: A cellular automaton model for wireless sensor networks. Journal of Cellular Automata, Vol. 7 (2012) 223--241.
• A. Salomaa, K. Salomaa, S. Yu: Undecidability of state complexity. International Journal of Computer Mathematics, to appear, doi:10.1080/00207160.2012.704994
• X. Piao, K. Salomaa: State complexity of the concatenation of regular tree languages. Theoretical Computer Science, Vol. 429 (2012) 273--281.
• C. Calude, K. Salomaa, T. Roblot: State-size hierarchy for finite-state complexity. International Journal of Foundations of Computer Science, Vol. 23, No. 1 (2012) 37--50.
• A. Okhotin, X. Piao, K. Salomaa: Descriptional complexity of input-driven pushdown automata. In: H. Bordihn, M. Kutrib, B. Truthe (Eds.) Dassow Festschrift 2012, Lect. Notes Comput. Sci., Vol. 7300, Springer-Verlag, 2012, pp. 186--206.
• Y.-S. Han, S.-K. Ko, K. Salomaa: Computing the edit distance between a regular language and a context-free language. Proceedings of the 16th International Conference Developments in Language Theory, DLT, (Taipei, Taiwan, August 14 - 17, 2012) Lect. Notes Comput. Sci. 7410, Springer-Verlag, 2012, pp. 85--96.
• A. Palioudakis, K. Salomaa, S.G. Akl: State complexity and limited nondeterminism. Proceedings of 14th International Workshop Descriptional Complexity of Formal Systems, DCFS, Lect. Notes Comput. Sci. 7386, Springer-Verlag, 2012, pp. 252--265.
• X. Piao, K. Salomaa: State complexity of projection and quotient on unranked trees. Proceedings of 14th International Workshop Descriptional Complexity of Formal Systems, DCFS, Lect. Notes Comput. Sci. 7386, Springer-Verlag, 2012, pp. 280--293.
• S. Choudhury, K. Salomaa, S.G. Akl: Cellular automaton based motion planning algorithms for mobile sensor networks. 1st International Conference on the Theory and Practice of Natural Computing (TPNC 2012), Tarragona, Spain, October 2--4, 2012, to appear in Springer Lecture Notes in Computer Science.
• S. Choudhury, K. Salomaa, S.G. Akl: Cellular automaton based algorithms for depth adjustment in underwater sensor networks. Proceedings of 6th International Workshop on Wireless Sensor, Actuator and Robot Networks, Las Vegas, October 2012.
• X. Piao, K. Salomaa: State complexity of Kleene-star operations on trees. Proceedings of WTCS 2012, (M.J. Dinneen, B. Khoussainov, A. Nies, Eds.) Lect. Notes Comput. Sci. 7160, Springer-Verlag, 2012, pp. 388--402.
• S. Choudhury, K. Salomaa, S.G. Akl: A cellular automaton model for connectivity preserving deployment of mobile wireless sensors. Proceedings of the 2nd IEEE International Workshop on Smart Communication Protocols and Algorithms (ICC'12 WS--SCPA), Ottawa, Canada, June 10--15, 2012.
• S. Choudhury, S.G. Akl, K. Salomaa: Energy efficient cellular automaton based algorithms for mobile sensor networks. Proceedings of the 2012 IEEE Wireless Communications and Networking Conference (WCNC 2012), Paris, France, April 1--4, 2012.
• K. Salomaa: Limitations of lower bound methods for deterministic nested word automata. Information and Computation, Vol. 209, No. 3 (2011) 580--589.
• Y. Gao, K. Salomaa, S. Yu: Transition complexity of incomplete DFAs. Fundamenta Informaticae, Vol. 110 (2011) 143--158.
• C. Calude, K. Salomaa, T. Roblot: Finite state complexity. Theoretical Computer Science, Vol. 412, No. 41 (2011) 5668--5677.
• X. Piao, K. Salomaa: Transformations between different models of unranked bottom-up tree automata. Fundamenta Informaticae, Vol. 109, No. 4, (2011) 405--424.
• Y.-S. Han, K. Salomaa: Overlap-free languages and solid codes. International Journal of Foundations of Computer Science, Vol. 22, No. 5 (2011) 1197--1209.
• M. Domaratzki, K. Salomaa: On language decompositions and primality. In: Rainbow of Computer Science, Lect. Notes Comput. Sci., Vol. 6570, Springer-Verlag, 2011, pp. 63--75.
• X. Piao, K. Salomaa: State trade-offs in unranked tree automata. Proceedings of 13th Workshop Descriptional Complexity of Formal Systems, DCFS'11, Lect. Notes Comput. Sci. 6808, Springer, 2011, pp. 261--274.
• X. Piao, K. Salomaa, S. V\'{a}gv\"{o}lgyi: Tree homomorphisms for unranked trees. Proceedings of the 13th International Conference on Automata and Formal Languages, AFL'11, (Pal Domosi, Szabolcs Ivan, Eds.) August 17--22, 2011, Debrecen, Hungary, pp. 343--357.
• A. Okhotin, K. Salomaa: State complexity of operations on input-driven pushdown automata, Proceedings of MFCS 2011, Lect. Notes Comput. Sci. 6907, Springer 2011, pp. 485--496.
• S. Choudhury, K. Salomaa, S.G. Akl: A cellular automaton model for wireless sensor networks, Proceedings of the 22nd IASTED International Symposium on Modelling and Simulation, Calgary, Alberta, Canada, July 4--6, 2011, pp. 190--195.
• D. Sears, K. Salomaa: Extended Watson-Crick L systems with regular trigger languages. Proceedings of the 10th International Conference on Unconventional Computation, UC'11, (J. Kari, I. Petre, Eds.), Lect. Notes Comput. Sci. 6714, Springer 2011, pp. 212--223.
• A. Okhotin, K. Salomaa: Descriptional complexity of unambiguous nested word automata. Proceedings of the 5th International Conference on Language and Automata Theory and Applications, LATA 2011, Tarragona, Spain, May 26--31, 2011. Lect. Notes Comput Sci. 6638, Springer 2011, pp. 414--426.
• A. Salomaa, K. Salomaa, S. Yu: Undecidability of the state complexity of composed regular operations. Proceedings of the 5th International Conference on Language and Automata Theory and Applications, LATA 2011, Tarragona, Spain, May 26--31, 2011. Lect. Notes Comput Sci. 6638, Springer 2011, pp. 489--498.
• A. Clarridge, K. Salomaa: Analysis of a cellular automaton model for car traffic with a slow-to-stop rule. Theoretical Computer Science, Vol. 411, No. 38--39, (2010) 3507--3515.
• M. Daley, M. Domaratzki, K. Salomaa: Orthogonal concatenation: Language equations and state complexity. Journal of Universal Computer Science, Vol. 16, No. 5, (2010) 653--675.
• A. Clarridge, K. Salomaa: An improved cellular automata based algorithm for the 45-convex hull problem. Journal of Cellular Automata, Vol. 5, No. 1--2, (2010) 107--120.
• X. Piao, K. Salomaa: Operational state-complexity of deterministic unranked tree automata. Proceedings of the 12th Workshop Descriptional Complexity of Formal Systems, DCFS 2010, (G. Pighizzini, I. McQuillan, B. Trost, Eds.), University of Saskatchewan, 2010, pp. 181--192.
• C.S. Calude, K. Salomaa, T. Roblot: Finite-state complexity and the size of transducers. Proceedings of the 12th Workshop Descriptional Complexity of Formal Systems, DCFS 2010, (G. Pighizzini, I. McQuillan, B. Trost, Eds.), University of Saskatchewan, 2010, pp. 50--61.
• Y. Gao, K. Salomaa, S. Yu: Transition complexity of incomplete DFA's. Proceedings of the 12th Workshop Descriptional Complexity of Formal Systems, DCFS 2010, (G. Pighizzini, I. McQuillan, B. Trost, Eds.), University of Saskatchewan, 2010, pp. 123--134.
• Y.-S. Han, K. Salomaa: Nondeterministic state complexity for suffix-free regular languages. Proceedings of the 12th Workshop Descriptional Complexity of Formal Systems, DCFS 2010, (G. Pighizzini, I. McQuillan, B. Trost, Eds.), University of Saskatchewan, 2010, pp. 236--244.
• X. Piao, K. Salomaa: Transformations between different types of unranked bottom-up tree automata. Proceedings of the 12th Workshop Descriptional Complexity of Formal Systems, DCFS 2010, (G. Pighizzini, I. McQuillan, B. Trost, Eds.), University of Saskatchewan, 2010, pp. 193--204.
• C. S. Calude, K. Salomaa, T. K. Roblot: Finite-state complexity and randomness. Programs, Proofs, Processes, 6th Conference on Computability in Europe, CiE 2010, Abstract and Handbook Booklet, (F. Ferreira, H. Guerra, E. Majordomo, J. Rasga, Eds.) Ponta Delgada, Azores, Portugal, University of Azores, 2010, pp. 73--82.

Edited volumes since 2010

• M. Domaratzki, K. Salomaa (Eds.), Special Issue: Implementation and Application of Automata (CIAA), International Journal of Foundations of Computer Science, Vol. 22, No. 8 (December 2011). (Preface pp. 1759--1760.)
• M. Domaratzki, K. Salomaa (Eds.), Implementation and Application of Automata, 15th International Conference, CIAA 2010, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 6482, Springer-Verlag, 2011.
• E. Csuhaj-Varj\'{u}, K. Salomaa (Eds.), Special Issue: {\em Computing with biomolecules,} Natural Computing, Vol. 10, No. 2 (2011). (Editorial pp. 775--776).
• M. Domaratzki, K. Salomaa (Eds.), {\em Pre-proceedings of the 15th International Conference on Implementation and Application of Automata, CIAA 2010,} Winnipeg, Manitoba, Canada, Aug. 12--15, 2010, ix + 325 pp.