Kai Salomaa: Publications up to 1994

• K. Salomaa, S. Yu: Measures of nondeterminism for pushdown automata. Journal of Computer and System Sciences, Vol. 49 (1994) 362-374.
• H. J\"{u}rgensen, K. Salomaa, S. Yu: Transducers and the decidability of independence in free monoids. Theoretical Computer Science, Vol. 134 (1994) 107-117.
• K. Salomaa: Synchronized tree automata. Theoretical Computer Science, Vol. 127 (1994) 25-51.
• K. Salomaa, D. Wood, S. Yu: Pumping and pushdown machines. RAIRO Theoretical Informatics and Applications, Vol. 28 (1994) 221-232.
• A. Ehrenfeucht, G. Rozenberg, K. Salomaa: Semantics of trees. Mathematical Systems Theory, Vol. 27 (1994) 159-181.
• T. Jiang, E. Kinber, A. Salomaa, K. Salomaa, S. Yu: Pattern languages with and without erasing. International Journal of Computer Mathematics, Vol. 50 (1994) 147-163.
• S. Yu, Q. Zhuang, K. Salomaa: The state complexities of some basic operations on regular languages. Theoretical Computer Science, Vol. 125 (1994) 315-328.
• L. Guo, K. Salomaa, S. Yu: Synchronization expressions and languages. Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing, (Dallas, Texas), IEEE Computer Society Press, 1994, pp. 257-264.
• K. Salomaa, D. Wood, S. Yu: Complexity of E0L structural equivalence. Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science, MFCS'94 (Kosice, Slovakia), Lect. Notes Comput. Sci. 841, Springer-Verlag, 1994, pp. 587-596.
• K. Salomaa, D. Wood, S. Yu: Rediscovering pushdown machines. Results and Trends in Theoretical Computer Science, Proceedings (Graz, Austria, June 1994), J. Karhu\-m\"aki, H. Maurer, G. Rozenberg (Eds.), Lect. Notes Comput. Sci. 812, Springer-Verlag, 1994, pp. 372-385.
• H. J\"{u}rgensen, K. Salomaa, S. Yu: Decidability of the intercode property. Journal of Information Processing and Cybernetics EIK, Vol. 29 (1993) 375-380.
• K. Salomaa, D. Wood, S. Yu: Structural equivalence and ET0L grammars. Proceedings of the 9th International Conference on Fundamentals of Computation Theory, FCT'93 (Szeged, Hungary), Lect. Notes Comput. Sci. 710, Springer-Verlag, 1993, pp. 430-439.
• T. Jiang, A. Salomaa, K. Salomaa, S. Yu: Inclusion is undecidable for pattern languages. Proceedings of the 20th International Colloquium on Automata, Languages and Programming, ICALP'93 (Lund, Sweden), Lect. Notes Comput. Sci. 700, Springer-Verlag, 1993, pp. 301-312.
• K. Salomaa, S. Yu: Limited nondeterminism for pushdown automata. Bulletin of the EATCS, Vol. 50 (1993) 186-193.
• K. Salomaa: Alternation bounds for tree automata. Acta Cybernetica, Vol. 10 (1992) 173-197.
• K. Salomaa: Confluence, ground confluence, and termination of monadic term rewriting systems. Journal of Information Processing and Cybernetics EIK, Vol. 28 (1992) 279-309.
• S. Yu, Q. Zhuang, K. Salomaa: Obtaining tight upper-bounds for the state complexities of DFA operations. Proceedings of the 4th International Conference on Computing and Information, ICCI'92 (Toronto, Canada), IEEE Computer Society Press, 1992, pp. 100-104.
• K. Salomaa, S. Yu: Decidability of structural equivalence of E0L grammars. Theoretical Computer Science, Vol. 82 (1991) 131-139.
• K. Salomaa, S. Yu: Degrees of nondeterminism for pushdown automata. Proceedings of the 8th International Conference on Fundamentals of Computation Theory, FCT'91 (Gosen, Germany), Lect. Notes Comput. Sci. 529, Springer-Verlag, 1991, pp. 380-389.
• K. Salomaa: Decidability of confluence and termination of monadic term rewriting systems. Proceedings of the 4th International Conference on Rewriting Techniques and Applications, RTA-91 (Como, Italy), Lect. Notes Comput. Sci. 488, Springer-Verlag, 1991, pp. 275-286.
• A. Salomaa, K. Salomaa, S. Yu: Primality types of instances of the Post Correspondence Problem. Bulletin of the EATCS, Vol. 44 (1991) 226-241.
• K. Salomaa, S. Yu: The immortality problem for Lag systems. Information Processing Letters, Vol. 36 (1990) 311-315.
• K. Salomaa: Hierarchy of $k$-context-free languages, Part 1. International Journal of Computer Mathematics, Vol. 26 (1989) 69-90.
• K. Salomaa: Hierarchy of $k$-context-free languages, Part 2. International Journal of Computer Mathematics, Vol. 26 (1989) 193-205.
• K. Salomaa: Representation of recursively enumerable languages using alternating finite tree recognizers. Proceedings of the 7th International Conference on Fundamentals of Computation Theory, FCT'89 (Szeged, Hungary), Lect. Notes Comput. Sci. 380, Springer-Verlag, 1989, pp. 372--383.
• K. Salomaa: k-parallel context-free grammars (in Finnish). Arkhimedes, Vol. 41 (1989) 139-148.
• K. Salomaa: A pumping result for 2-context-free languages. Theoretical Computer Science, Vol. 62 (1988) 267-287.
• K. Salomaa: Deterministic tree pushdown automata and monadic tree rewriting systems. Journal of Computer and System Sciences, Vol. 37 (1988) 367-394.
• K. Salomaa: Yield-languages recognized by alternating tree recognizers. RAIRO Theoretical Informatics and Applications, Vol. 22 (1988) 319-339.
• K. Salomaa: Alternating tree pushdown automata. Annales Universitatis Turkuensis, Ser.~A1 Vol. 192 (1988) 1-30.
• K. Salomaa, M. Stern: A note on the group-theoretic isomorphism theorems. Publicationes Mathematicae, Vol. 33 (1986) 235-237.
• K. Salomaa: Alternating bottom-up tree recognizers. Proceedings of the 11th Colloquium on Trees in Algebra and Programming, CAAP'86 (Nice, France,} Lect. Notes Comput. Sci. 214, Springer-Verlag, 1986, pp. 158-171.
• H. C. M. Kleijn, M. Penttonen, G. Rozenberg, K. Salomaa: Direction independent context-sensitive grammars. Information and Control, Vol. 63 (1984) 113-117.