Kai Salomaa | Academic Influence

Kai Salomaa's AcademicInfluence.com Rankings

Kai Salomaa

Computer Science

#5093

World Rank

#5380

Historical Rank

computer-science Degrees

Kai Salomaa

Mathematics

#7690

World Rank

#10434

Historical Rank

Measure Theory

#3192

World Rank

#3779

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Kai Salomaa's Degrees

Masters Mathematics University of Helsinki
Bachelors Mathematics University of Helsinki

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is Kai Salomaa Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Kai T. Salomaa is a Finnish Canadian theoretical computer scientist, known for his numerous contributions to the state complexity of finite automata. His highly cited 1994 joint paper with Yu and Zhuang laid the foundations of the area. He has published over 100 papers in scientific journals on various subjects in formal language theory. Salomaa is a full professor at Queen's University .

(See a Problem?)

Kai Salomaa's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

The State Complexities of Some Basic Operations on Regular Languages (1994) (333)
A sharpening of the Parikh mapping (2001) (125)
State Complexity of Basic Operations on Finite Languages (1999) (111)
State complexity of combined operations (2007) (88)
Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems (1988) (87)
Decision Problems for Patterns (1995) (86)
A Formal Study Of Practical Regular Expressions (2003) (84)
Tight Lower Bound for the State Complexity of Shuffle of Regular Languages (2002) (73)
State complexity of basic operations on suffix-free regular languages (2007) (65)
Pattern languages with and without erasing (1994) (56)
The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal (2008) (51)
NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets (1998) (50)
Lexical Analysis with a Simple Finite-Fuzzy-Automaton Model (1995) (49)
On the State Complexity of k-Entry Deterministic Finite Automata (2001) (45)
Operational State Complexity of Prefix-Free Regular Languages (2009) (44)
Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages (2009) (39)
Complexity of input-driven pushdown automata (2014) (35)
Inclusion is Undecidable for Pattern Languages (1993) (35)
Metric Lexical Analysis (1999) (34)
Operational state complexity of nested word automata (2009) (33)
State Complexity of Union and Intersection of Finite Languages (2007) (32)
On the descriptional complexity of Watson-Crick automata (2009) (32)
Finite state complexity (2011) (31)
State complexity of operations on input-driven pushdown automata (2011) (30)
On the State Complexity of Combined Operations and their Estimation (2007) (30)
Analysis of a cellular automaton model for car traffic with a slow-to-stop rule (2010) (29)
Nondeterministic state complexity of nested word automata (2009) (28)
Descriptional Complexity of Formal Systems (2016) (26)
Transition Complexity of Incomplete DFAs (2010) (25)
Decidability of trajectory-based equations (2005) (24)
Additive Distances and Quasi-Distances Between Words (2002) (23)
A Cellular Automaton Model for Wireless Sensor Networks (2012) (23)
Energy efficient cellular automaton based algorithms for mobile wireless sensor networks (2012) (23)
The Edit-Distance between a Regular Language and a Context-Free Language (2012) (22)
Improved Recruitment Algorithms for Vehicular Crowdsensing Networks (2019) (22)
Descriptional Complexity of Nondeterministic Finite Automata (2007) (20)
Synchronization expressions and languages (1994) (20)
State Complexity of Prefix-Free Regular Languages (2006) (19)
On Synchronization Languages (1996) (19)
On an Extension of the Parikh Mapping (2000) (18)
State Complexity of Finite Tree Width NFAs (2012) (17)
Undecidability of the State Complexity of Composed Regular Operations (2011) (17)
Trajectory-based operations (2004) (17)
Limitations of lower bound methods for deterministic nested word automata (2011) (16)
Ambiguity, Nondeterminism and State Complexity of Finite Automata (2017) (16)
Transition complexity of language operations (2007) (16)
State Complexity of Shuffle on Trajectories (2004) (16)
On the existence of prime decompositions (2007) (16)
Transformations Between Different Models of Unranked Bottom-Up Tree Automata (2010) (15)
Synchronized Tree Automata (1994) (15)
Lower bounds for the transition complexity of NFAs (2006) (15)
State Complexity of Regular Languages: Finite versus Infinite (2000) (15)
A cellular automaton model for connectivity preserving deployment of mobile wireless sensors (2012) (15)
Orthogonal Concatenation: Language Equations and State Complexity (2010) (14)
Shuffle Quotient and Decompositions (2001) (14)
State Complexity of Orthogonal Catenation (2009) (14)
Descriptional complexity of unambiguous input-driven pushdown automata (2015) (14)
Nondeterministic State Complexity for Suffix-Free Regular Languages (2010) (14)
CARRE: Cellular automaton based redundant readers elimination in RFID networks (2016) (13)
Alternating finite automata and star-free languages (2000) (13)
Measures of Nondeterminism for Pushdown Automata (1994) (13)
Comparisons between Measures of Nondeterminism on Finite Automata (2013) (13)
State Complexity of Neighbourhoods and Approximate Pattern Matching (2015) (13)
Transducers and the Decidability of Independence in Free Monoids (1994) (13)
Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks (2014) (13)
State Complexity of Combined Operations for Prefix-Free Regular Languages (2009) (13)
Descriptional Complexity of Input-Driven Pushdown Automata (2012) (12)
Cellular Automaton Based Motion Planning Algorithms for Mobile Sensor Networks (2012) (12)
On the existence of regular approximations (2007) (12)
Codes defined by multiple sets of trajectories (2006) (12)
A Cryptosystem Based on the Composition of Reversible Cellular Automata (2009) (12)
Synchronization Expressions with Extended Join Operation (1998) (11)
State Complexity and Limited Nondeterminism (2012) (11)
Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata (2000) (11)
Hierarchy of k-context-free languages (1989) (11)
Prime Decompositions of Regular Languages (2006) (11)
Finite-State Complexity and Randomness (2009) (11)
Decidability of Structural Equivalence of E0L Grammars (1991) (10)
Descriptional Complexity of Unambiguous Nested Word Automata (2011) (10)
Approximate matching between a context-free grammar and a finite-state automaton (2013) (10)
Shuffle Decompositions of Regular Languages (2002) (10)
State Complexity of Additive Weighted Finite Automata (2007) (10)
Finite-State Complexity and the Size of Transducers (2010) (9)
Restricted sets of trajectories and decidability of shuffle decompositions (2005) (9)
Pumping and Pushdown Machines (1994) (9)
Variants of codes and indecomposable languages (2009) (9)
State Complexity of Catenation and Reversal Combined with Star (2006) (9)
NFA to DFA Transformation for Finite Languages (1996) (9)
Decidability of Confluence and Termination of Monadic Term Rewriting Systems (1991) (9)
Decidability of the Intercode Property (1993) (9)
Intercode Regular Languages (2007) (8)
State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages (2013) (8)
State Trade-Offs in Unranked Tree Automata (2011) (8)
An Improved Cellular Automata Based Algorithm for the 45-Convex Hull Problem (2010) (8)
On the Inverse Beacon Attraction Region of a Point (2015) (8)
State complexity of the concatenation of regular tree languages (2012) (8)
Localized algorithms for redundant readers elimination in RFID networks (2019) (8)
State Complexity of Kleene-Star Operations on Trees (2012) (7)
State complexity of permutation on finite languages over a binary alphabet (2017) (7)
Complexity of E0L Structural Equivalence (1994) (7)
Watson-Crick automata: determinism and state complexity (2008) (7)
Routing in a Polygonal Terrain with the Shortest Beacon Watchtower (2018) (7)
Edit Distance Neighbourhoods of Input-Driven Pushdown Automata (2017) (7)
On Fairness of Many-Dimensional Trajectories (2000) (7)
Length Codes, Products of Languages and Primality (2008) (7)
A Cellular Automaton Model for Car Traffic with a Slow-to-Stop Rule (2009) (7)
Branching Measures and Nearly Acyclic NFAs (2017) (7)
Undecidability of state complexity (2013) (6)
Alternating Finite Automata with Limited Universal Branching (2020) (6)
Unary NFAs with Limited Nondeterminism (2014) (6)
Operational State Complexity of Deterministic Unranked Tree Automata (2010) (6)
Primary Types of Instances of the Post Correspondence Problem (1991) (6)
Interpreted Trajectories (2006) (6)
Structural Equivalence and ET0L Grammars (1996) (6)
State Complexity of Insertion (2016) (6)
State complexity of prefix distance (2015) (6)
Cellular Automaton Based Localized Algorithms for Mobile Sensor Networks (2015) (5)
Proceedings of the 15th international conference on Implementation and application of automata (2004) (5)
One-Visit Caterpillar Tree Automata (2002) (5)
Yield-Languages Recognized by Alternating Tree Recognizers (1988) (5)
Cellular automata and object monitoring in mobile wireless sensor networks (2015) (5)
Iterated TGR Languages: Membership Problem and Effective Closure Properties (2006) (5)
The Length of the Beacon Attraction Trajectory (2016) (5)
Quantifying Nondeterminism in Finite Automata (2015) (5)
Direction Independent Context-Sensitive Grammars (1986) (5)
The State Complexity of Permutations on Finite Languages over Binary Alphabets (2015) (5)
Nondeterminism Growth and State Complexity (2019) (5)
State-Size Hierarchy for Finite-State Complexity (2012) (5)
Efficient Implementation of Regular Languages Using R-AFA (1997) (5)
Pseudo-inversion on Formal Languages (2014) (5)
Input-Driven Pushdown Automata with Limited Nondeterminism - (Invited Paper) (2014) (4)
On the Size of Stack and Synchronization Alphabets of Tree Automata (1998) (4)
State complexity of deletion and bipolar deletion (2016) (4)
Duplications and Pseudo-Duplications (2015) (4)
Site-Directed Insertion: Decision Problems, Maximality and Minimality (2018) (4)
Decision Problems for Restricted Variants of Two-Dimensional Automata (2019) (4)
Implementing Reversed Alternating Finite Automaton (r-AFA) Operations (1998) (4)
Quasi-Distances and Weighted Finite Automata (2015) (4)
State complexity of inversion operations (2014) (4)
Lower Bound for Converting an NFA with Finite Nondeterminism into an MDFA (2014) (4)
Nondeterministic State Complexity of Proportional Removals (2013) (4)
Outfix-guided insertion (2017) (4)
Operational state complexity of unary NFAs with finite nondeterminism (2016) (4)
Yield-Languages of Two-Way Pushdown Tree Automata (1996) (4)
Lower bounds for the size of deterministic unranked tree automata (2012) (3)
Cellular automata and Mobile Wireless Sensor Networks (2014) (3)
Consensus String Problem for Multiple Regular Languages (2020) (3)
The Quotient Operation on Input-Driven Pushdown Automata (2017) (3)
Unary NFAs, Limited Nondeterminism, and Chrobak Normal Form (2015) (3)
Regex and extended regex (2002) (3)
The Relative Edit-Distance Between Two Input-Driven Languages (2019) (3)
State Complexity of Nested Word Automata (2009) (3)
Top-down tree edit-distance of regular tree languages (2014) (3)
Descriptional Complexity of Error Detection (2017) (3)
Overlap-Free Languages and solid Codes (2011) (3)
Nondeterminism Degrees for Context-Free Languages (1995) (3)
Degrees of Nondeterminism for Pushdown Automata (1991) (3)
P, NP and the Post Correspondence Problem (1995) (3)
Worst Case Branching and Other Measures of Nondeterminism (2017) (3)
Confluence, ground confluence, and termination of monadic term rewriting systems (1992) (2)
Nondeterministic Tree Width of Regular Languages (2015) (2)
Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata (2020) (2)
Decidability of Equivalence for Deterministic Synchronized Tree Automata (1995) (2)
Computation Width and Deviation Number (2014) (2)
Decidability of fairness for context-free languages (1997) (2)
Cycle Height of Finite Automata (2018) (2)
Further Closure Properties of Input-Driven Pushdown Automata (2019) (2)
Semantics of Nonsequential Tree-Based Computation Schemes (1997) (2)
On Language Decompositions and Primality (2011) (2)
Preface Program Committee Automaton Models Inspired by Peptide Computing (2007) (2)
Rewriting Rules for Synchronization Languages (1997) (2)
Deciding determinism of caterpillar expressions (2009) (2)
Deterministic Caterpillar Expressions (2007) (2)
Input-driven pushdown automata: nondeterminism and unambiguity (2013) (2)
Technical Report No. 2011-577 State Complexity of Star and Quotient Operation for Unranked Tree Automata (2011) (2)
Structural Equivalences and ET0L Grammars (Extended Abstract) (1993) (2)
Extended Watson–Crick L systems with regular trigger languages and restricted derivation modes (2012) (2)
Representation of Recursively Enumerable Languages Using Alternating Finite Tree Recognizers (1989) (2)
Morphisms and rational tranducers (1993) (2)
Obtaining tight upper-bounds for the state complexities of DFA operations (1992) (2)
Synchronization Expressions: Characterization Results and Implementation (1999) (2)
Rediscovering Pushdown Machines (1994) (2)
Language Decompositions, Primality, and Trajectory-Based Operations (2008) (2)
State Complexity of Unary Language Operations for NFAs with Limited Nondeterminism (2014) (2)
Concatenation Operations and Restricted Variants of Two-Dimensional Automata (2020) (2)
Hierarchy of k-context-free languages part 1 (1989) (2)
Alternating Bottom-Up Tree Recognisers (1986) (2)
Finite Nondeterminism vs. DFAs with Multiple Initial States (2013) (2)
State Complexity of Projection and Quotient on Unranked Trees (2012) (1)
Decidability of EDT0L structural equivalence (2002) (1)
Structural Equivalence and ETOL grammars (1993) (1)
On Simon's Congruence Closure of a String (2022) (1)
Growth Rate of Minimum Branching (2018) (1)
Alternation Bounds for Tree Automata (1992) (1)
An online fair resource allocation solution for fog computing (2022) (1)
State Complexity of Prefix Distance of Subregular Languages (2016) (1)
On the Modularity of Decidability of Completeness and Termination (1996) (1)
Regular Approximations of Non-Regular Languages (2006) (1)
Tree Homomorphisms for Unranked Trees (2011) (1)
Pseudoknot-generating operation (2016) (1)
Sheng Yu (1950-2012) In Memoriam (2012) (1)
Generalizations of Code Languages with Marginal Errors (2015) (1)
Contextual Grammars with Uniform Sets of Trajectories (2004) (1)
Structural properties of NFAs and growth rates of nondeterminism measures (2021) (1)
State Complexity of Kleene-Star Operations on Regular Tree Languages (2015) (1)
Site-Directed Deletion (2018) (1)
An infinite hierarchy induced by depth synchronization (2007) (1)
Semantics of trees (1994) (1)
Goodby to the Kindhearted Dragon Prof. Sheng Yu, 1950-2012 (2013) (1)
Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata (2020) (1)
Comparison of Genetic Operators for the Multiobjective Pickup and Delivery Problem (2022) (1)
Deciding path size of nondeterministic (and input-driven) pushdown automata (2022) (0)
Hierarchies of synchronized and algebraic forests (1997) (0)
Resource Optimization of SFC Embedding for IoT Networks Using Quantum Computing (2022) (0)
Generalized Fairness and Context-Free Languages (1999) (0)
A Two-Stage Based Strategy to Optimize Homeless Placement in Shelters (2022) (0)
Report on the Magic in Science symposium (2017) (0)
Site-directed insertion: Language equations and decision problems (2019) (0)
Relative Prefix Distance Between Languages (2017) (0)
Decision problems and projection languages for restricted variants of two-dimensional automata (2020) (0)
Structural Equivalence of Regularly Extended E0L Grammars: An Automata Theoretic Proof (2004) (0)
Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity (2019) (0)
Series Finite-State Complexity and Randomness (2010) (0)
Top-down tree edit-distance of regular tree languages (2018) (0)
State complexity of deletion and bipolar deletion (2015) (0)
Pseudo-inversion: closure properties and decidability (2015) (0)
EDTOL Structural Equivalence is Decidable (1996) (0)
Outfix-Guided Insertion - (Extended Abstract) (2016) (0)
Multi-Objective Task Assignment Solution for Parked Vehicular Computing (2023) (0)
State Complexity of Deletion (2014) (0)
Descriptional Complexity of Finite Automata - Selected Highlights (2023) (0)
State Complexity of the Quotient Operation on Input-Driven Pushdown Automata (2019) (0)
Advances and Trends in Automata and Formal Languages A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen - J.UCS Special Issue (2002) (0)
Cellular automaton based algorithms for depth adjustment in underwater mobile sensor networks (2012) (0)
Width Measures of Alternating Finite Automata (2021) (0)
A note on the group-theoretic isomorphism theorems (2022) (0)
Pseudo-inversion: closure properties and decidability (2016) (0)
Descriptional complexity of unambiguous input-driven pushdown (2012) (0)
One-Visit Caterpillar Tree (2002) (0)
Editorial: Computing with biomolecules (2011) (0)
Decidabi l i ty of Equivalence for Determini s t i c Synchronized Tree A u t o m a t a (2005) (0)
Degrees of Restriction for Two-Dimensional Automata (2021) (0)
Shu e Quotient and Decompositions ? (2007) (0)
State Complexity of k-Parallel Tree Concatenation (2017) (0)
Closest Substring Problems for Regular Languages (2018) (0)
COMPLEXITY OF PREFIX DISTANCE OF SUBREGULAR LANGUAGES (2017) (0)
Extended Watson–Crick L systems with regular trigger languages and restricted derivation modes (2011) (0)
Preface (2011) (0)
COMPLEXITY OF PREFIX DISTANCE OF SUBREGULAR LANGUAGES (2017) (0)
Preface (2005) (0)
In Memoriam Sheng Yu (2012) (0)
State Complexity of Suffix Distance (2019) (0)
Nondeterministic State Complexity of Site-Directed Deletion (2022) (0)
State Complexity of Unranked Tree Automata (2010) (0)
Implementation and Application of Automata (2016) (0)
Technical Report No . 2010-567 State Complexity of Unranked Tree Automata (2010) (0)
Nondeterministic State Complexity of Site-Directed Insertion (2022) (0)
International workshop on omputing with biomolecules. Wien, 2008 (2008) (0)
Boolean grammars: expressive power and parsing algorithms (2005) (0)
On the synchronized derivation depth of context-free grammars (2009) (0)
The Immortality Problem for LAG Systems (1990) (0)

This paper list is powered by the following services:

Other Resources About Kai Salomaa

What Schools Are Affiliated With Kai Salomaa?

Kai Salomaa is affiliated with the following schools:

Image Attributions

Image Source for Kai Salomaa