Publications

Kai Salomaa: Publications 2000--2004

M. Domaratzki, K. Salomaa: State complexity of shuffle on trajectories. Journal of Automata, Languages and Combinatorics, Vol. 9 Nr. 2/3 (2004) 217-232.
M. Domaratzki, K. Salomaa: Decidability of trajectory-based equations. Proceedings of 29th International Symposium on Mathematical Foundations of Computer Science, MFCS 2004, Prague, Czech Republic, August 22--27, 2004, Lect. Notes Comput. Sci. 3153 Springer-Verlag, 2004, pp. 723-734. (Technical report.)
K. Salomaa: Patterns, in: ``Formal Languages and Applications: Studies in Fuzziness and Soft Computing 148'', C. Martin-Vide, V. Mitrana, Gh. Paun (Eds.), Springer, Berlin, 2004, pp. 367-379.
K. Salomaa, D. Wood: Structural equivalence of regularly extended E0L grammars: An automata theoretic proof. In: ``Theory is Forever'', J. Karhum\"aki, H. Maurer, G. Paun, G. Rozenberg (Eds.), Lect. Notes in Comput. Sci. 3113 , Springer-Verlag, 2004, pp. 259 - 267.
M. Domaratzki, K. Salomaa: Restricted sets of trajectories and decidability of shuffle decompositions. Proceedings of Descriptional Complexity of Formal Systems, 6th Workshop, DCFS'04, L. Ilie, D. Wotschke (Eds.), London, Ontario, July 26 - 28, 2004, pp. 37 - 51.
M. Domaratzki, A. Mateescu, K. Salomaa, S. Yu: Deletion on trajectories and commutative closure, Proceedings of 4th International Conference on WORDS, T. Harju, J. Karhumaki (Eds.), Turku, Finland, Sept. 10 - 13, 2003, pp. 309 - 319.
C. Campeanu, K. Salomaa, S. Yu: A formal study of practical regular expressions, International Journal of Foundations of Computer Science, Vol. 14 (2003) 1007 - 1018.
A. Okhotin, K. Salomaa, M. Domaratzki: One-visit caterpillar tree automata, Fundamenta Informaticae, Vol. 52 (2002) 361 - 375.
M. Domaratzki, K. Salomaa: State-complexity of shuffle on trajectories, Proceedings of of DCFS'02, (J. Dassow, M. Hoeberechts, H. Jurgensen, D. Wotschke, Eds.), London, Ontario, August 21 - 24, 2002, pp. 95 - 109.
C. Campeanu, K. Salomaa, S. Yu: Tight lower bound for the state complexity of shuffle of regular languages, Journal of Automata, Languages and Combinatorics, Vol. 7 (2002) 303 -310.
C. Campeanu, K. Salomaa, S. Vagvolgyi: Shuffle decompositions of regular languages. International Journal of Foundations of Computer Science, Vol. 13 (2002) 799 - 816.
C. Campeanu, K. Salomaa, S. Yu: Regex and extended regex, Proceedings of CIAA'02, (Tours, France, July 3 - 5, 2002), J.-M. Champarnaud, D. Maurel (Eds.), pp. 81 - 89.
C.S. Calude, K. Salomaa, S. Yu: Additive distances and quasi-distances between words. Journal of Universal Computer Science, Vol. 8 (2002) 141 - 152.
K. Salomaa, S. Yu: 276 (2002) 245 - 259.
A. Mateescu, A. Salomaa, K. Salomaa, S. Yu: A sharpening of the Parikh mapping. RAIRO Theoretical Informatics, to appear.
C. Campeanu, K. Salomaa, S. Vagvolgyi: Shuffle quotient and decompositions, Developments in Language Theory, 5th International Conference, DLT2001, (Wien, 16 - 21 July 2001). Revised papers. Lect. Notes Comput. Sci. 2295, Springer-Verlag 2002, pp. 186 - 196.
M. Holzer, K. Salomaa, S. Yu: On the state complexity of k-entry deterministic finite automata, Journal of Automata, Languages and Combinatorics, Vol. 6 (2001) 453 - 466. (A preliminary version appeared in Proceedings of DCAGRS 2000, Descriptional Complexity of Automata, Grammars and Related Structures, O. Boldt, H. Jurgensen (Eds.), July 2000.)
C. Campeanu, K. Culik II, K. Salomaa, S. Yu: State complexity of basic operations on finite languages, Automata Implementation. Fourth International Workshop on Implementing Automata, WIA'99, (Potsdam, Germany). Revised papers, O. Boldt, H. Jurgensen (Eds.), Lect. Notes Comput. Sci. 2214, Springer-Verlag, 2001, pp. 60 - 70.
C.S. Calude, K. Salomaa, S. Yu: Metric lexical analysis. Automata Implementation, Fourth International Workshop on Implementing Automata, WIA'99, (Potsdam, Germany). Revised papers, O. Boldt, H. Jurgensen (Eds.), Lect. Notes Comput. Sci. 2214, Springer-Verlag, 2001, pp. 48 - 59.
K. Salomaa, S. Yu: Alternating finite automata and star-free languages. Theoretical Computer Science, Vol. 234 (2000) 167-176.
A. Mateescu, K. Salomaa, S. Yu: On fairness of many-dimensional trajectories. Journal of Automata, Languages and Combinatorics, Vol. 5 (2000) 145-157.
C. C\^ampeanu, K. Salomaa, S. Yu: State complexity of regular languages: Finite versus infinite. In: ``Finite vs Infinite: Contributions to an Eternal Dilemma'', C. S. Calude, G. Paun (Eds.), Springer-Verlag, 2000, pp. 53-73.
K. Salomaa, X. Wu, S. Yu: Efficient implementation of regular languages with reversed alternating finite automata. Theoretical Computer Science, Vol. 231 (2000) 103-111.