Publications by Arto Salomaa before 1990
(Books in italics)
-
1959
-
On many-valued systems of logic. Ajatus 22, 115 -159.
-
1960
-
On the composition of functions of several variables ranging over a
finite set. Ann. Univ. Turku, Ser. A I 41, 48 pp.
-
A theorem concerning the composition of functions of several variables
ranging over a finite set. Journal of Symbolic Logic 25, 203--8.
-
1962
-
On the number of simple bases of the set of functions over a finite
domain. Ann. Univ. Turku, Ser. A I 52, 4 pp.
-
Some completeness criteria for sets of functions over a finite domain, I.
Ibid., Ser. A I 53, 10 pp.
-
1963
-
Some completeness criteria for sets of functions over a finite domain,
II. Ibid., Ser. A I 63, 19 pp. (Russian translations of two previous
papers in Kibernetitseskii sbornik 8 (1964), 8--32.)
-
On sequences of functions over an arbitrary domain. Ibid., Ser. A I 62, 5
pp.
-
Some analogues of Sheffer functions in infinite-valued logics. Proc.
Colloq. Modal and Many-valued Logics in Helsinki 1962, 227--235.
-
On basic groups for the set of functions over a finite domain. Ann.
Acad. Scient. Fennicae, Ser. A I 338, 15 pp.
-
On essential variables of functions, especially in the algebra of
logic. Ibid., Ser. A I 339, 11 pp.
-
1964
-
Theorems on the representation of events in Moore automata. Ann. Univ.
Turku, Ser. A I 69, 14 pp.
-
On infinitely generated sets of operations in finite algebras. Ibid.,
Ser. A I 74, 13 pp.
-
Axiom systems for regular expressions of finite automata. Ibid., Ser. A I
75, 29 pp.
-
On the reducibility of events represented in automata. Ann. Acad.
Scient. Fennicae, Ser. A I 353, 16 pp.
-
1965
-
On the heights of closed sets of operations in finite algebras. Ibid.,
Ser. A I 363, 12 pp.
-
On some algebraic notions in the theory of truthfunctions. Acta Philos.
Fennica 18, 193--202.
-
On probabilistic automata with one input letter. Ann. Univ. Turku, Ser. A
I 85, 16 pp.
-
Automaattien teoriasta. Arkhimedes, 7--20.
-
1966
-
Two complete axiom systems for the algebra of regular events. Journal of
the Association for Computing Machinery 13, 158--169.
-
Aksiomatizatsija algebry sobytii, realizuemyh logitseskimi setjami.
Problemy Kibernetiki 17, 237--246.
-
1967
-
On $m$-adic probabilistic automata. Information and Control 10, 215--19.
-
Formal languages. Lecture Notes for the Research Seminar on Computer
Science, Univ. of Toronto, 58 pp.
-
1968
-
On events represented by probabilistic automata of different types.
Canadian Journal of Mathematics 20, 242--251.
-
On languages accepted by probabilistic and time-variant automata. Proc. II
Princeton Conf. On Information Sciences and Systems 184--188.
-
(with V. Tixier) Two complete axiom systems for the extended language of
regular expressions. IEEE Computer Trans. C-17, 700--701.
-
On finite automata with a time-variant structure. Information and
Control 13, 85--98.
-
On finite time-variant automata with monitors of different types. Ann.
Univ. Turku, Ser. A I 118:3, 12 pp.
-
On regular expressions and regular canonical systems. Mathematical
Systems Theory 2, 341--355.
-
Matematiikka ja tietokone. Arkhimedes, 5--10.
-
1969
-
"Theory of Automata". International Series of Monographs in Pure
and
Applied Mathematics, Vol. 100, Pergamon Press, 276 pp. Japanese
translation by Kyoritsu Shuppan in 1974.
-
On the index of a context-free grammar and language. Information and
Control 14, 474--477.
-
Probabilistic and time-variant grammars and languages. Avh.
Forsta Nordiska Logikersymposiet, 115--133.
-
On grammars with restricted use of productions. Ann. Acad. Scient.
Fennicae, Ser. A I 454, 32 pp.
-
1970
-
On some families of formal languages obtained by regulated derivations.
Ibid., Ser. A I 479, 18 pp.
-
Probabilistic and weighted grammars. Information and Control 15,
529--544.
-
Periodically time-variant context-free grammars. Ibid., 17, 294--311.
-
1971
-
The generative capacity of transformational grammars of Ginsburg and
Partee. Ibid., 18, 227--232.
-
Theories of abstract automata (review). Ibid., 19, 476--478.
-
Grammars with control languages. Mathematisch Instituut, Utrecht, publ.
no. 7, 8 pp.
-
1972
-
Matrix grammars with a leftmost restriction. Information and Control
20, 143--149.
-
On a homomorphic characterization of recursively enumerable languages.
Ann. Acad. Sci. Fennicae, Ser. A I 525, 10 pp.
-
1973
-
"Formal Languages". Academic Press, New York, 335 pp.
-
On exponential growth in Lindenmayer systems. Indagationes Mathematicae
35, 23--30.
-
On sentential forms of context-free grammars. Acta Informatica 2,
40--49.
-
(with A. Paz) Integral sequential word functions and growth equivalence of
Lindenmayer systems. Information and Control 23, 313--343.
-
Macros, iterated substitution and Lindenmayer AFL's. Aarhus University
DAIMI Publications 18, 13 pp.
-
On some decidability problems concerning developmental languages. Proc.
3rd Scandinavian Logic Symposium, North-Holland Publ. Co. (1975), pp.
144--153.
-
Growth functions associated with some new types of grammars. Proc.
Conf. on Algebraic Theory of Automata, Szeged, 27--31.
-
On some recent problems concerning developmental languages. Proc. 1.
Fachtagung \"uber Automatentheorie und formale Sprachen, Springer Lecture
Notes in Computer Science, Vol. 2, 23--34.
-
L-systems: a device in biologically motivated automata theory. Proc.
Conf. on Mathematical Foundations of Computer Science, Slovak Academy
of Sciences, 147--151.
-
Developmental languages: a new type of formal languages. Ann. Univ.
Turku, Ser. B 126, pp. 183--189.
-
1974
-
Solution of a decision problem concerning unary Lindenmayer systems.
Discrete Mathematics 9, 71--77.
-
Some remarks concerning many-valued propositional logics. In: S.
Stenlund (ed.), Logical Theory and Semantical Analysis, D. Reidel Publ.
Co., 15--21.
-
(with M. Nielsen, G. Rozenberg and S. Skyum) Nonterminals,
homomorphisms and codings in different variations of $OL$-systems, Parts
I-II. Acta Informatica 3, pp. 357-364, and 4, pp. 87--106.
-
(with G. Rozenberg) The mathematical theory of L systems. Aarhus
University DAIMI Publications 33, 67 pp., extended version appears also
in: J. Tou (ed.), Advances in Information Systems Science, Vol. 6,
Plenum Press (1976), pp. 161--206.
-
Recent results on L-systems. Proc. Conf. on Biologically Motivated
Automata Theory, IEEE Publications no. 74 CH0 889-6 C, pp. 38--45.
-
Parallelism in rewriting systems. Proc. 2nd Colloquium on Automata,
Languages and Programming, Springer Lecture Notes in Computer Science,
Vol. 14, 523--533.
-
(edited with G. Rozenberg) ``L Systems". Springer Lecture Notes in
Computer Science, Vol. 15, 338 pp.
-
Iteration grammars and Lindenmayer AFL's. Previous Volume, pp. 250--253.
-
1975
-
Formal power series and growth functions of Lindenmayer systems.
Springer Lecture Notes in Computer Science, Vol. 32, pp. 101--113.
-
Comparative decision problems between sequential and parallel
rewriting. Proc. Intern. Symp. Uniformly Structured Automata and Logic,
IEEE Publications 75 CH1 052-0 C, pp. 62--66.
-
Growth functions of Lindenmayer systems: some new approaches. In:
Automata, Languages and Development, North-Holland (1976), pp. 271--282.
-
Tietokoneiden tulo. In: Luonnontieteellisen tutkimuksen historia. WSOY,
Porvoo, Finland, pp. 245--256.
-
1976
-
(with G. Rozenberg) Context-free grammars with graph-controlled tables.
Journal of Computer and System Sciences 13, pp. 90--99.
-
(with G. Rozenberg and K. Ruohonen) Developmental systems with
fragmentation. International Journal of Computer Mathematics 5, pp.
177--191.
-
L systems: A parallel way of looking at formal languages. New ideas and
recent developments. Mathematical Centre Tracts 82, Amsterdam, pp.
65--107.
-
Sequential and parallel rewriting. In: R. Aguilar (ed.), Formal
Languages and Programming. North-Holland, pp. 111--129.
-
Undecidable problems concerning growth in informationless Lindenmayer
systems. Elektronische Informationsverarbeitung und Kybernetik 12,
pp. 331--335.
-
Recent results on L systems. Springer Lecture Notes in Computer
Science, Vol. 45, pp. 115--123.
-
1977
-
(with G. Rozenberg) New squeezing mechanisms for L systems. Information
Sciences 12, pp. 187--201.
-
Formal power series and language theory. Nanyang University
Publications, 23 pp.
-
(with H. Maurer and D. Wood) E0L forms. Acta Informatica 8, pp. 75--96.
-
(with H. Maurer and Th. Ottman) On the form equivalence of L forms.
Theoretical Computer Science 4, pp. 199--225.
-
(with M. Penttonen and G. Rozenberg) Bibliography of L systems.
Theoretical Computer Science 5, pp. 339--354.
-
(ed. with M. Steinby) Automata, Languages and Programming. Proc. 4th
ICALP Conference in Turku. Springer Lecture Notes in Computer Science,
Vol. 52, 569 pp.
-
1978
-
(with M. Soittola) Automata-Theoretic Aspects of Formal Power
Series. Springer-Verlag, New York, 181 pp.
-
(with H. Maurer and D. Wood) On good E0L forms. SIAM Journal of
Computing, Vol. 7, pp. 158--166.
-
(with H. Maurer and D. Wood) Uniform interpretations of L forms.
Information and Control 36, pp. 157--173.
-
(with H. Maurer and D. Wood) ET0L forms. Journal of Computer and System
Sciences, Vol. 16, pp. 345--361.
-
(with K. Culik, H. Maurer, Th. Ottman and K. Ruohonen) Isomorphism,
form equivalence and sequence equivalence of PD0L forms. Theoretical
Computer Science 6, pp. 143--173.
-
(with H. Maurer and D. Wood) Relative goodness of E0L forms.
RAIRO/Theoretical Computer Science, Vol. 12, pp. 291--304.
-
D0L equivalence: The problem of iterated morphisms. EATCS Bulletin 4,
pp. 5--12.
-
L systems and L forms. Journal of the Computer Society of India, Vol. 8,
pp. 23--30.
-
Equality sets for homomorphisms of free monoids. Acta Cybernetica Vol. 4,
pp. 127--139.
-
(with K. Culik) On the decidability of homomorphism equivalence for
languages. Journal of Computer and System Sciences 17, pp. 163--175.
-
1979
-
(with H. Maurer, M. Penttonen and D. Wood) On non context-free grammar
forms. Mathematical Systems Theory 12, pp. 297--324.
-
Formale Sprachen. Springer-Verlag, Berlin-Heidelberg-New York, 314
pp. (Translation of "Formal Languages".)
-
D0L language equivalence. EATCS Bulletin 8, pp. 4--12.
-
Power from power series. Springer-Verlag Lecture Notes in Computer
Science, Vol. 74, pp. 170--181.
-
Language theory based on parallelism: old and new results about L
systems. Proceedings of the Fourth IBM Symposium on Mathematical
Foundations of Computer Science (Oiso, Japan), pp. 1--20.
-
(with H. Maurer, G. Rozenberg and D. Wood) Pure interpretations of E0L
forms. RAIRO/Theoretical Computer Science, Vol. 13, pp. 347--362.
-
(with H. Maurer and D. Wood) Context-dependent L forms. Information and
Control 42, pp. 97--118.
-
Sata vuotta matemaattista logiikkaa: paattelysaannoista
tietokoneohjelmointiin. In: Muuttuvat ajat, WSOY, Porvoo, Finland,
pp. 116--130.
-
1980
-
(with G. Rozenberg) The Mathematical Theory of L Systems. Academic
Press, New York, xvi$+$352 pp.
-
Morphisms on free monoids and language theory. In R. Book (ed.) Formal
Language Theory, Academic Press, pp. 141--166.
-
(with H. Maurer and D. Wood) Synchronized E0L forms. Theoretical
Computer Science, Vol. 12, pp. 135--159.
-
(with H. Maurer and D. Wood) Pure grammars. Information and Control 44,
pp. 47--72.
-
(with H. Maurer and D. Wood) On generators and generative capacity of
E0L forms. Acta Informatica 13, pp. 87--107.
-
(with K. Culik) Test sets and checking words for homomorphism
equivalence. Journal of Computer and System Sciences, Vol. 20, pp.
379--395.
-
(with H. Maurer and D. Wood) Context-free grammar forms with strict
interpretations. Journal of Computer and System Sciences, Vol. 21,
pp. 110--135.
-
Grammatical families. Springer Lecture Notes in Computer Science, Vol.
85, pp. 543--554.
-
(with H. Maurer and D. Wood) MSW spaces. Information and Control 46,
pp. 187--199.
-
1981
-
Jewels of Formal Language Theory. Computer Science Press,
Potomac, Maryland, x$+$144 pp.
-
(with H. Maurer and D. Wood) Derivation languages of grammar forms,
Journal of Computer Mathematics Section A, Vol. 9, pp. 117--130.
-
(with H. Maurer and D. Wood) Colorings and interpretations: a
connection between graphs and grammar forms, Discrete Applied Mathematics
3, pp. 119--135.
-
(with H. Maurer and D. Wood) Decidability and density in two-symbol
grammar forms, Discrete Applied Mathematics 3, pp. 289--299.
-
(with H. Maurer and D. Wood) Uniform interpretations of grammar forms,
SIAM Journal of Computing, Vol. 10, pp. 483--502.
-
(with Th. Ottman and D. Wood) Sub-regular grammar forms, Information
Processing Letters, Vol. 12, pp. 184--187.
-
Salakirjoitus ja tietosuoja --- nakymia kryptografian
tutkimuksesta.
Arkhimedes, Vol. 33, pp. 129--135.
-
What computer scientists should know about sauna? European Association
for Theoretical Computer Science Bulletin, Vol. 15, pp. 8--21.
-
(with H. Maurer and D. Wood) Synchronized E0L forms under uniform
interpretation. RAIRO/Theoretical Computer Science, Vol. 15 (1981),
pp. 337--353.
-
(with H. Maurer and D. Wood) Completeness of context-free grammar
forms, Journal of Computer and System Sciences, 23, pp. 1--10.
-
(with G. Rozenberg) Table systems with unconditional transfer. Discrete
Applied Mathematics 3, pp. 319--322.
-
Formal power series in noncommuting variables. Proceedings of the 18th
Scandinavian Congress for Mathematicians, Birkhauser, 104--124.
-
On color-families of graphs. Annales Academiae Scientiarum Fennicae,
Ser. A I, 6, 135--148.
-
(with J. Maenpaa and G. Rozenberg) Bibliography of L systems.
Leiden
University Computer Science Technical Report.
-
1982
-
(with H. Maurer and D. Wood) Dense hierarchies of grammatical families.
Journal of the Association for Computing Machinery 29, 118--126.
-
(with K. Culik and F.E. Fich) A homomorphic characterization of regular
languages. Discrete Applied Mathematics 4, 149--152.
-
(with K. Culik and J. Gruska) On non-regular context-free languages and
pumping. Bulletin of the European Association for Theoretical
Computer Science, Number 16, pp. 22--24.
-
(with H. Maurer and D. Wood) On predecessors of finite languages.
Information and Control 50, 259--275.
-
(with K. Culik) On infinite words obtained by iterating morphisms.
Theoretical Computer Science 19, 29--38.
-
(with H. Maurer and D. Wood) Finitary and infinitary interpretations of
languages. Mathematical Systems Theory 15, 251--265.
-
1983
-
(with K. Culik and J. Gruska) Systolic Automata for VLSI on balanced
trees. Acta Informatica 18, 335--344.
-
(with H. Maurer and D. Wood) L codes and number systems. Theoretical
Computer Science 22, 331--346.
-
(with H. Maurer and D. Wood) A supernormal-form theorem for
context-free grammars. Journal of the Association for Computing Machinery
30, 95--102.
-
(with J. Honkala) How do you define the complement of a language. EATCS
Bulletin 20, 68--69.
-
(with H. Maurer and D. Wood) On finite grammar forms. International
Journal of Computer Mathematics 12, 227--240.
-
(with K. Culik and J. Gruska) On a family of L languages resulting from
systolic tree automata. Theoretical Computer Science 23, 231--242.
-
(with K. Culik) Ambiguity and decision problems concerning number
systems. Springer Lecture Notes in Computer Science 154, 137--146.
-
1984
-
(with K. Culik and J. Gruska) Systolic trellis automata, I and II.
International Journal of Computer Mathematics 15, 195--212 and 16, 3--22.
-
Trapdoors and protocols: recent trends in cryptography. In: H. Maurer
(ed.) ``\"Uberblicke Informationsverarbeitung 1984". Bibliographisches
Institut Mannheim-Wien-Z\"urich, 275--320.
-
(with K. Culik and D. Wood) Systolic tree acceptors. RAIRO 18, 53--69.
-
(with K. Culik) Ambiguity and decision problems concerning number
systems. Information and Control 56, 139--153.
-
Julkiset salat. Tiede 2000 9-10, 46--52.
-
(ed. with W. Brauer and G. Rozenberg) 3 volumes of EATCS Monographs on
Theoretical Computer Science, Springer-Verlag.
-
1985
-
Computation and Automata. Encyclopedia of Mathematics and
Its Applications, Vol. 25. Cambridge University Press, Cambridge and
New York, XIII$+$282 pp.
-
(with H. J\"urgensen) Syntactic monoids in the construction of systolic
tree automata. International Journal of Computer and Information Sciences
14, 35--49.
-
On a public-key cryptosystem based on parallel rewriting. Parcella-84,
Proceedings of the International Conference on Parallel Processing,
Berlin, 209--214.
-
Cryptography from Caesar to DES and RSA. EATCS Bulletin 26, 101--119.
-
The Ehrenfeucht conjecture: a proof for language theorists. EATCS
Bulletin 27, 71--82.
-
Generalized number systems: decidability, ambiguity, codes. Proceedings of
the 19th Nordic Congress of Mathematicians, Reykjavik, 213--214.
-
Tietosuojauksen kehittaminen. Matemaattisten aineiden aikakauskirja
49,
283--291.
-
On meta-normal forms for algebraic power series in noncommuting
variables. Annales Academiae Scientiarum Fennicae, Ser. Al, Vol. 10,
501--510.
-
(ed. with G. Rozenberg) The Book of L. Springer-Verlag, Berlin and New
York, xv$+$471 pp.
-
(with G. Rozenberg) When L was young. In: G. Rozenberg, A. Salomaa
(eds.) The Book of L, Springer-Verlag, 383--392.
-
(ed. with W. Brauer and G. Rozenberg) 2 volumes of EATCS Monographs on
Theoretical Computer Science, Springer-Verlag.
-
1986
-
(with W. Kuich) Semirings, Automata, Languages. EATCS Monographs
on Theoretical Computer Science, Vol. 5, Springer-Verlag, Berlin and New
York, vi$+$374 pp.
-
(ed. with J. Demetrovics and G. Katona) Algebra, Combinatorics and
Logic in Computer Science, I-II. North-Holland, Amsterdam and New York,
887 pp.
-
Systolic tree and trellis automata. In: J. Demetrovics, G. Katona,
A. Salomaa (eds.) Algebra, Combinatorics and Logic in Computer
Science, North-Holland, 695--710.
-
Zhemtsuzhiny teorii formalnykh jazykov. Izd. "Mir", Moscow, 159
pp. (Translation of "Jewels of Formal Language Theory".)
-
(with E. Kinber and Sheng Yu) On the equivalence of grammars inferred
from derivations. EATCS Bulletin 29, 39--46.
-
(with K. Culik and J. Gruska) Systolic trellis automata: stability,
decidability and complexity. Information and Control 71, 218--230.
-
(with H. Maurer, E. Welzl and D. Wood) Denseness, maximality and
decidability of grammatical families. Annales Academiae Scientiarum
Fennicae, Ser. Al, Vol. 11, 167--178.
-
(with Sheng Yu) On a public-key cryptosystem based on iterated
morphisms and substitutions. Theoretical Computer Science 48, 283--296.
-
(ed. with W. Brauer and G. Rozenberg) 3 volumes of EATCS Monographs on
Theoretical Computer Science, Springer-Verlag.
-
1987
-
Markov algorithms as language-defining devices. In: ``The Very Knowledge
of Coding", Univ. of Turku, 120--127.
-
(with S. Horvath, E. Kinber and Sheng Yu) Decision problems resulting
from grammatical inference. Annales Academiae Scientiarum Fennicae, Vol.
12, 287--298.
-
Two-way Thue. EATCS Bulletin 32, 82--86.
-
Playfair. EATCS Bulletin 33, 42--53.
-
(ed. with W. Brauer and G. Rozenberg) 2 volumes of EATCS Monographs on
Theoretical Computer Science, Springer-Verlag.
-
1988
-
On a public-key cryptosystem based on language theory. Computers and
Security, Vol. 7, 83--87.
-
L codes: variations on a theme of MSW. In IIG Report 260, Ten years of
IIG, 218.
-
Cryptography and natural languages. EATCS Bulletin 35, 92--96.
-
COSTOC: Tietokoneavusteisen opetuksen projekti. Korkeakoulujen
ATK-Uutiset 2/88, 8--10.
-
(ed. with T. Lepisto) Automata, Languages and Programming, Proc.
of
ICALP-88. Springer Lecture Notes in Computer Science, Vol. 317, 741 pp.
-
Computation and Automata. Japanese translation. Information
and Computing -28. x$+$332 pp.
-
Computation and Automata. HyperCOSTOC Computer Science, Vol. 5.
Hofbauer Verlag AG. 84 pp. and 10 discs.
-
Cryptography and Data Security. HyperCOSTOC Computer Science, Vol. 32.
Hofbauer Verlag AG. 41 pp. and 5 discs.
-
Cryptographic Transductions. EATCS Bulletin 36, 85--95.
-
(ed. with W. Brauer and G. Rozenberg) 6 volumes of EATCS Monographs on
Theoretical Computer Science, Springer-Verlag.
-
1989
-
Knapsacks and superdogs. EATCS Bulletin 38, 107--123.
-
Tutorial: Cryptography and data security. Springer Lecture Notes in
Computer Science, Vol. 381, 220--244.
-
Public-key cryptosystems and language theory. A Perspective in
Theoretical Computer Science. Commemorative Volume for Gift Siromoney.
World Scientific, Series in Computer Science, Vol. 16, 257--266.
-
(with G. Rozenberg) Complexity theory. In Encyclopaedia of Mathematics,
Vol. 2, 280--283. Kluwer Academic Publishers.
-
(with G. Rozenberg) Cryptography. In Encyclopaedia of Mathematics, Vol. 2,
466-468. Kluwer Academic Publishers.
-
(with G. Rozenberg) Formal languages and automata. In Encyclopaedia of
Mathematics, Vol. 4, 53--57. Kluwer Academic Publishers.
-
(ed. with W. Brauer and G. Rozenberg) 2 volumes of EATCS Monographs on
Theoretical Computer Science, Springer-Verlag.