Arto Salomaa
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Arto Salomaa has a total of 36 co-authors. Here are the top co-authors by number of shared publications:
- Gheorghe Păun
Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucharest, Romania
15 shared publications - Grzegorz Rozenberg
Universiteit Leiden
12 shared publications - Sheng Yu
Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7
4 shared publications - Alexandru Mateescu
University of Bucharest
3 shared publications - Kai Salomaa
School of Computing, Queen’s University, Kingston, Canada
3 shared publications A. Mateescu
Turku Centre for Computer Science (TUCS) Finland and Faculty of Mathematics , University of Bucharest , Turku, 20520, Romania
2 shared publications
Latest Publications
- Open Access
- 30 December 2020
- Published by TechForum Publishing Group in Bulletin of Computer and Data Sciences
- Vol. 1 (1) , 19-26
From Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity
We study Parikh matrices as an order-sensitive refinement of Parikh vectors. We formalize the mapping \(PM_k\) and an indicator-based generalization \(PM_v\), showing via a simple encoding that every \(PM_v\) reduces to an ordinary Parikh matrix. Structurally, we revisit \(M\)-equivalence and (un)ambiguity (including the complete binary characterization and finiteness for prints), and identify cyclic shifts and disjoint transpositions as Parikh-friendly permutations. Algorithmically, \(M\)-equivalence is decidable in polynomial time, while recognition and unambiguity admit natural exponential procedures; superdiagonals exhibit substantial independence. Finally, we construct binary families with exponentially large \(M\)-equivalence classes and relate their counts to Gaussian binomials, ruling out polynomial upper bounds on ambiguity degree.- 30 December 2020
- Published by TechForum Publishing Group in Bulletin of Computer and Data Sciences
- Vol. 1 (1) , 19-26
Open AccessFrom Parikh Vectors to Parikh Matrices: Structure, Ambiguity, and Complexity
We study Parikh matrices as an order-sensitive refinement of Parikh vectors. We formalize the mapping \(PM_k\) and an indicator-based generalization \(PM_v\), showing via a simple encoding that every \(PM_v\) reduces to an ordinary Parikh matrix. Structurally, we revisit \(M\)-equivalence and (un)ambiguity (including the complete binary characterization and finiteness for prints), and identify cyclic shifts and disjoint transpositions as Parikh-friendly permutations. Algorithmically, \(M\)-equivalence is decidable in polynomial time, while recognition and unambiguity admit natural exponential procedures; superdiagonals exhibit substantial independence. Finally, we construct binary families with exponentially large \(M\)-equivalence classes and relate their counts to Gaussian binomials, ruling out polynomial upper bounds on ambiguity degree. - 1 December 2020
- Published by Springer Nature in Journal of Membrane Computing
- Vol. 2 (4) , 227-229
Preface of the special issue for Gheorghe Paun's 70th anniversary
- 1 December 2020
- Published by Springer Nature in Journal of Membrane Computing
- Vol. 2 (4) , 227-229
Preface of the special issue for Gheorghe Paun's 70th anniversary
- 9 August 2018
- Published by Springer Nature
- p. 100-112
Parikh Matrices: Subword Indicators and Degrees of Ambiguity
- 9 August 2018
- Published by Springer Nature
- p. 100-112
Parikh Matrices: Subword Indicators and Degrees of Ambiguity
- Open Access
- 1 January 2015
- Published by University of Szeged in Acta Cybernetica
- Vol. 22 (2) , 247-257
Two-Step Simulations of Reaction Systems by Minimal Ones
Reaction systems were introduced by Ehrenfeucht and Rozenberg with biochemical applications in mind. The model is suitable for the study of subset functions, that is, functions from the set of all subsets of a finite set into itself. In this study the number of resources of a reaction system is essential for questions concerning generative capacity. While all functions (with a couple of trivial exceptions) from the set of subsets of a finite set S into itself can be defined if the number of resources is unrestricted, only a specific subclass of such functions is defined by minimal reaction systems, that is, the number of resources is smallest possible. On the other hand, minimal reaction systems constitute a very elegant model. In this paper we simulate arbitrary reaction systems by minimal ones in two derivation steps. Various techniques for doing this consist of taking names of reactions or names of subsets as elements of the background set. In this way also subset functions not at all definable by reaction systems can be generated. We follow the original definition of reaction systems, where both reactant and inhibitor sets are assumed to be nonempty.
- 1 January 2015
- Published by University of Szeged in Acta Cybernetica
- Vol. 22 (2) , 247-257
Open AccessTwo-Step Simulations of Reaction Systems by Minimal Ones
Reaction systems were introduced by Ehrenfeucht and Rozenberg with biochemical applications in mind. The model is suitable for the study of subset functions, that is, functions from the set of all subsets of a finite set into itself. In this study the number of resources of a reaction system is essential for questions concerning generative capacity. While all functions (with a couple of trivial exceptions) from the set of subsets of a finite set S into itself can be defined if the number of resources is unrestricted, only a specific subclass of such functions is defined by minimal reaction systems, that is, the number of resources is smallest possible. On the other hand, minimal reaction systems constitute a very elegant model. In this paper we simulate arbitrary reaction systems by minimal ones in two derivation steps. Various techniques for doing this consist of taking names of reactions or names of subsets as elements of the background set. In this way also subset functions not at all definable by reaction systems can be generated. We follow the original definition of reaction systems, where both reactant and inhibitor sets are assumed to be nonempty.
- 10 December 2014
- Published by Springer Nature
- p. 436-446
Minimal Reaction Systems Defining Subset Functions
- 10 December 2014
- Published by Springer Nature
- p. 436-446
Minimal Reaction Systems Defining Subset Functions
- 11 May 2013
- Published by Springer Nature in Natural Computing
- Vol. 12 (3) , 369-376
Minimal and almost minimal reaction systems
- 11 May 2013
- Published by Springer Nature in Natural Computing
- Vol. 12 (3) , 369-376
Minimal and almost minimal reaction systems
- 1 October 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 454, 2-4
Preface
- 11 May 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 432, 85-93
Subword occurrences, weighted automata and iterated morphisms, especially the Fibonacci morphism
- 11 May 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 432, 85-93
Subword occurrences, weighted automata and iterated morphisms, especially the Fibonacci morphism
- 1 January 2012
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 116 (1-4) , 237-249
Mirror Images and Schemes for the Maximal Complexity of Nondeterminism
We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n . The construction leads to cases, where
- 1 January 2012
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 116 (1-4) , 237-249
Mirror Images and Schemes for the Maximal Complexity of Nondeterminism
We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n . The construction leads to cases, where
- 1 January 2012
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 120 (1) , 71-74
Sheng Yu (1950–2012) In Memoriam
- 1 January 2012
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 120 (1) , 71-74
Sheng Yu (1950–2012) In Memoriam