Edit Profile (opens in new tab) Salomaa, Kai T. Co-Author Distance Author ID: salomaa.kai-t Published as: Salomaa, Kai; Salomaa, K.; Salomaa, Kai T. more...less External Links: MGP · Wikidata · dblp · GND · IdRef Documents Indexed: 241 Publications since 1984 8 Contributions as Editor Co-Authors: 60 Co-Authors with 226 Joint Publications 1,106 Co-Co-Authors all top 5 Co-Authors 22 single-authored 58 Yu, Sheng 56 Han, Yo-Sub 29 Ko, Sang-Ki 21 Ng, Timothy 18 Salomaa, Arto Kustaa 17 Domaratzki, Michael 15 Okhotin, Alexander 15 Palioudakis, Alexandros 14 Cho, Da-Jung 13 Rappaport, David 13 Wood, Derick 12 Piao, Xiaoxue 10 Akl, Selim G. 9 Smith, Taylor J. 7 Câmpeanu, Cezar 7 Keeler, Chris 6 Mateescu, Alexandru 5 Calude, Cristian S. 5 Goč, Daniel 4 Clarridge, Adam G. 4 Gao, Yuan 4 Kim, Hwee 4 Kim, Sungmin 4 Rozenberg, Grzegorz 3 Jiang, Tao 3 Jürgensen, Helmut 3 Lyon, Oliver A. S. 3 Roblot, Tania K. 3 Vágvölgyi, Sándor 2 Biegler, Franziska 2 Daley, Mark 2 Ehrenfeucht, Andrzej 2 Eom, Hae-Sung 2 Kang, Shin-Dong 2 Keeler, Casey 2 McQuillan, Ian 2 Rahonis, George 2 Sears, David R. W. 2 Szilard, Andrew L. 2 Wu, Xiuming 2 Zan, Jinfeng 1 Cheon, Hyunjoon 1 Choudhury, Salimur 1 Cordy, Brendan J. 1 Culik, Karel II 1 Czeizler, Elena 1 Czeizler, Eugen 1 Fülöp, Zoltán 1 Guo, Lifu 1 Holzer, Markus 1 Huerter, Sandra 1 Kari, Lila 1 Kinber, Efim B. 1 Kleijn, Jetty 1 Kouhestani, Bahram 1 Penttonen, Martti 1 Stern, Manfred 1 Zakzok, Mohammad 1 Zhuang, Qingyu 1 Zu, Sheng all top 5 Serials 45 Theoretical Computer Science 23 International Journal of Foundations of Computer Science 12 Journal of Automata, Languages and Combinatorics 11 Fundamenta Informaticae 6 Information and Computation 5 Journal of Computer and System Sciences 4 Acta Cybernetica 4 International Journal of Computer Mathematics 4 Journal of Universal Computer Science 3 Annales Societatis Mathematicae Polonae. Series IV 3 RAIRO. Informatique Théorique et Applications 3 Lecture Notes in Computer Science 2 Information Processing Letters 2 Publicationes Mathematicae Debrecen 2 Journal of Information Processing and Cybernetics 2 Bulletin of the European Association for Theoretical Computer Science (EATCS) 2 Natural Computing 1 Acta Informatica 1 Arkhimedes 1 Information and Control 1 Mathematical Systems Theory 1 Computational Geometry 1 RAIRO. Theoretical Informatics and Applications 1 Annales Universitatis Turkuensis. Ser. A I 1 Scientific Annals of Computer Science 1 Journal of Cellular Automata all top 5 Fields 245 Computer science (68-XX) 8 General and overarching topics; collections (00-XX) 6 Mathematical logic and foundations (03-XX) 6 Biology and other natural sciences (92-XX) 4 History and biography (01-XX) 2 Information and communication theory, circuits (94-XX) 1 Combinatorics (05-XX) 1 Group theory and generalizations (20-XX) 1 Convex and discrete geometry (52-XX) 1 Numerical analysis (65-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 181 Publications have been cited 1,288 times in 652 Documents Cited by ▼ Year ▼ The state complexities of some basic operations on regular languages. Zbl 0795.68112 Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai 159 1994 A sharpening of the Parikh mapping. Zbl 1005.68092 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 73 2001 State complexity of combined operations. Zbl 1124.68056 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 40 2007 Decision problems for patterns. Zbl 0827.68066 Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 37 1995 A formal study of practical regular expressions. Zbl 1101.68443 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 36 2003 State complexity of basic operations on finite languages. Zbl 1050.68091 Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 35 2001 State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033 Han, Yo-Sub; Salomaa, Kai 34 2009 Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 31 2002 Pattern languages with and without erasing. Zbl 0939.68690 Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 27 1994 Deterministic tree pushdown automata and monadic tree rewriting systems. Zbl 0668.68084 Salomaa, Kai 26 1988 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060 Salomaa, Kai; Yu, Sheng 24 1997 Operational state complexity of prefix-free regular languages. Zbl 1182.68105 Han, Yo-Sub; Salomaa, Kai; Wood, Derick 21 2009 Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534 Han, Yo-Sub; Salomaa, Kai; Wood, Derick 20 2009 Operational state complexity of nested word automata. Zbl 1176.68108 Piao, Xiaoxue; Salomaa, Kai 18 2009 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093 Holzer, Markus; Salomaa, Kai; Yu, Sheng 17 2001 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040 Gao, Yuan; Salomaa, Kai; Yu, Sheng 17 2008 Nondeterministic state complexity of nested word automata. Zbl 1173.68034 Han, Yo-Sub; Salomaa, Kai 16 2009 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 0960.68611 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai 16 1995 Additive distances and quasi-distances between words. Zbl 1258.68074 Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 16 2002 The edit-distance between a regular language and a context-free language. Zbl 1293.68187 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 15 2013 On the state complexity of combined operations and their estimations. Zbl 1149.68397 Salomaa, Kai; Zu, Sheng 15 2007 State complexity of union and intersection of finite languages. Zbl 1155.68037 Han, Yo-Sub; Salomaa, Kai 14 2008 On the existence of prime decompositions. Zbl 1111.68055 Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 14 2007 On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169 Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai 13 2009 State complexity of additive weighted finite automata. Zbl 1183.68354 Salomaa, Kai; Schofield, Paul 11 2007 Decidability of trajectory-based equations. Zbl 1079.68049 Domaratzki, Michael; Salomaa, Kai 11 2005 Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044 Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai 11 2017 Finite state complexity. Zbl 1235.68088 Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 10 2011 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224 Okhotin, Alexander; Salomaa, Kai 10 2014 Inclusion is undecidable for pattern languages. Zbl 1422.68152 Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 10 1993 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186 Okhotin, Alexander; Salomaa, Kai 10 2017 Limited nondeterminism for pushdown automata. Zbl 1023.68621 Salomaa, Kai; Yu, Sheng 9 1993 Nondeterministic state complexity for suffix-free regular languages. Zbl 1455.68091 Han, Yo-Sub; Salomaa, Kai 9 2010 Transition complexity of incomplete DFAs. Zbl 1230.68130 Gao, Yuan; Salomaa, Kai; Yu, Sheng 9 2011 State complexity of finite tree width NFAs. Zbl 1322.68126 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 9 2012 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111 Okhotin, Alexander; Salomaa, Kai 9 2015 Shuffle decompositions of regular languages. Zbl 1067.68085 Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 9 2002 State complexity of permutation on finite languages over a binary alphabet. Zbl 1371.68145 Cho, Da-Jung; Goč, Daniel; Han, Yo-Sub; Ko, Sang-Ki; Palioudakis, Alexandros; Salomaa, Kai 9 2017 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 Measures of nondeterminism for pushdown automata. Zbl 0822.68070 Salomaa, Kai; Yu, Sheng 8 1994 Patterns. Zbl 1089.68059 Salomaa, Kai 8 2004 Transition complexity of language operations. Zbl 1143.68033 Domaratzki, Michael; Salomaa, Kai 7 2007 Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141 Daley, M.; Domaratzki, M.; Salomaa, K. 7 2010 State complexity of insertion. Zbl 1404.68069 Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 7 2016 Codes defined by multiple sets of trajectories. Zbl 1154.68066 Domaratzki, Michael; Salomaa, Kai 7 2006 Transducers and the decidability of independence in free monoids. Zbl 0938.68710 Jürgensen, H.; Salomaa, K.; Yu, S. 6 1994 Lower bounds for the transition complexity of NFAs. Zbl 1152.68028 Domaratzki, Michael; Salomaa, Kai 6 2008 Descriptional complexity of nondeterministic finite automata. Zbl 1202.68239 Salomaa, Kai 6 2007 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147 Okhotin, Alexander; Salomaa, Kai 6 2011 Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136 Salomaa, Kai 6 2011 Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235 Piao, Xiaoxue; Salomaa, Kai 6 2011 Outfix-guided insertion. Zbl 1382.68133 Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai 6 2017 Quasi-distances and weighted finite automata. Zbl 1432.68239 Ng, Timothy; Rappaport, David; Salomaa, Kai 6 2015 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039 Salomaa, Kai; Yu, Sheng 6 1991 State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159 Ng, Timothy; Rappaport, David; Salomaa, Kai 6 2018 Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050 Kouhestani, Bahram; Rappaport, David; Salomaa, Kai 6 2018 On fairness of many-dimensional trajectories. Zbl 0959.68068 Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 6 2000 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1489.68133 Okhotin, Alexander; Salomaa, Kai 6 2017 Alternating finite automata and star-free languages. Zbl 0944.68090 Salomaa, K.; Yu, S. 5 2000 Primality types of instances of the Post correspondence problem. Zbl 0744.68083 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Pumping and pushdown machines. Zbl 0883.68093 Salomaa, Kai; Wood, D.; Yu, Sheng 5 1994 Prime decompositions of regular languages. Zbl 1227.68057 Han, Yo-Sub; Salomaa, Kai; Wood, Derick 5 2006 Synchronized tree automata. Zbl 0805.68084 Salomaa, Kai 5 1994 Cellular automaton based motion planning algorithms for mobile sensor networks. Zbl 1374.68309 Choudhury, Salimur; Salomaa, Kai; Akl, Selim G. 5 2012 State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096 Ng, Timothy; Rappaport, David; Salomaa, Kai 5 2015 State complexity of deletion and bipolar deletion. Zbl 1335.68121 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 5 2016 Intercode regular languages. Zbl 1111.68056 Han, Yo-Sub; Salomaa, Kai; Wood, Derick 5 2007 Decidability of the intercode property. Zbl 0824.68061 Jürgensen, H.; Salomaa, K.; Yu, S. 4 1993 Nondeterminism growth and state complexity. Zbl 1434.68268 Keeler, Chris; Salomaa, Kai 4 2019 Decision problems for restricted variants of two-dimensional automata. Zbl 1434.68288 Smith, Taylor J.; Salomaa, Kai 4 2019 On Simon’s congruence closure of a string. Zbl 07643468 Kim, Sungmin; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 4 2022 Structural equivalence and ET0L grammars. Zbl 0794.68093 Salomaa, Kai; Wood, Derick; Yu, Sheng 4 1993 On synchronization languages. Zbl 0843.68055 Guo, L.; Salomaa, K.; Yu, S. 4 1996 Pseudo-inversion on formal languages. Zbl 1445.68121 Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai 4 2014 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317 Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 4 2016 State complexity of shuffle on trajectories. Zbl 1098.68068 Domaratzki, Michael; Salomaa, Kai 4 2004 Restricted sets of trajectories and decidability of shuffle decompositions. Zbl 1080.68053 Domaratzki, Michael; Salomaa, Kai 4 2005 Branching measures and nearly acyclic NFAs. Zbl 1426.68147 Keeler, Chris; Salomaa, Kai 4 2017 Recognition and complexity results for projection languages of two-dimensional automata. Zbl 07371301 Smith, Taylor J.; Salomaa, Kai 3 2020 Iterated TGR languages: membership problem and effective closure properties. Zbl 1162.68473 McQuillan, Ian; Salomaa, Kai; Daley, Mark 3 2006 Block-synchronization context-free grammars. Zbl 0867.68077 Jürgensen, Helmut; Salomaa, Kai 3 1997 Site-directed insertion: decision problems, maximality and minimality. Zbl 1435.68152 Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 3 2018 Decision problems and projection languages for restricted variants of two-dimensional automata. Zbl 1504.68116 Smith, Taylor J.; Salomaa, Kai 3 2021 Structural properties of NFAs and growth rates of nondeterminism measures. Zbl 1537.68074 Keeler, Chris; Salomaa, Kai 3 2022 State complexity and limited nondeterminism. Zbl 1304.68117 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2012 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176 Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 3 2012 Lower bounds for the transition complexity of NFAs (extended abstract). Zbl 1132.68441 Domaratzki, Michael; Salomaa, Kai 3 2006 On the existence of regular approximations. Zbl 1143.68032 Cordy, Brendan; Salomaa, Kai 3 2007 State trade-offs in unranked tree automata. Zbl 1341.68106 Piao, Xiaoxue; Salomaa, Kai 3 2011 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1388.68168 Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 3 2013 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2013 Comparisons between measures of nondeterminism on finite automata. Zbl 1388.68177 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2013 State complexity of prefix distance. Zbl 1371.68160 Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2015 Operational state complexity of unary NFAs with finite nondeterminism. Zbl 1332.68125 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2016 Generalizations of code languages with marginal errors. Zbl 1434.68255 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2015 Worst case branching and other measures of nondeterminism. Zbl 1371.68163 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2017 Descriptional complexity of error detection. Zbl 1396.68068 Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2017 State complexity of basic operations on suffix-free regular languages. Zbl 1147.68559 Han, Yo-Sub; Salomaa, Kai 3 2007 Site-directed deletion. Zbl 1517.68180 Cho, Da-Jung; Han, Yo-Sub; Kim, Hwee; Salomaa, Kai 3 2018 Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes. Zbl 1331.68139 Sears, David; Salomaa, Kai 3 2012 Descriptional complexity of finite automata – selected highlights. Zbl 1547.68378 Salomaa, Arto; Salomaa, Kai; Smith, Taylor J. 1 2024 On the Simon’s congruence neighborhood of languages. Zbl 07766942 Kim, Sungmin; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2023 Deciding path size of nondeterministic (and input-driven) pushdown automata. Zbl 1543.68170 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2023 Existential and universal width of alternating finite automata. Zbl 07729457 Han, Yo-Sub; Kim, Sungmin; Ko, Sang-Ki; Salomaa, Kai 1 2023 On Simon’s congruence closure of a string. Zbl 1520.68059 Kim, Sungmin; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2023 Recognition and complexity results for projection languages of two-dimensional automata. Zbl 07770057 Smith, Taylor J.; Salomaa, Kai 1 2023 Maximal existential and universal width. Zbl 07897389 Keeler, Casey; Salomaa, Kai 1 2023 On Simon’s congruence closure of a string. Zbl 07643468 Kim, Sungmin; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 4 2022 Structural properties of NFAs and growth rates of nondeterminism measures. Zbl 1537.68074 Keeler, Chris; Salomaa, Kai 3 2022 Nondeterministic state complexity of site-directed insertion. Zbl 07584602 Lyon, Oliver A. S.; Salomaa, Kai 1 2022 Decision problems and projection languages for restricted variants of two-dimensional automata. Zbl 1504.68116 Smith, Taylor J.; Salomaa, Kai 3 2021 Concatenation operations and restricted variants of two-dimensional automata. Zbl 1490.68130 Smith, Taylor J.; Salomaa, Kai 2 2021 Generalizations of code languages with marginal errors. Zbl 1522.68277 Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 2 2021 Width measures of alternating finite automata. Zbl 07614744 Keeler, Casey; Salomaa, Kai 1 2021 Consensus string problem for multiple regular languages. Zbl 1497.68269 Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 1 2021 Recognition and complexity results for projection languages of two-dimensional automata. Zbl 07371301 Smith, Taylor J.; Salomaa, Kai 3 2020 Combining limited parallelism and nondeterminism in alternating finite automata. Zbl 07371292 Keeler, Chris; Salomaa, Kai 2 2020 Alternating finite automata with limited universal branching. Zbl 1437.68099 Keeler, Chris; Salomaa, Kai 2 2020 Nondeterminism growth and state complexity. Zbl 1434.68268 Keeler, Chris; Salomaa, Kai 4 2019 Decision problems for restricted variants of two-dimensional automata. Zbl 1434.68288 Smith, Taylor J.; Salomaa, Kai 4 2019 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1423.68262 Okhotin, Alexander; Salomaa, Kai 3 2019 Site-directed insertion: language equations and decision problems. Zbl 1435.68151 Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 3 2019 The relative edit-distance between two input-driven languages. Zbl 1534.68085 Cheon, Hyunjoon; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2019 State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159 Ng, Timothy; Rappaport, David; Salomaa, Kai 6 2018 Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050 Kouhestani, Bahram; Rappaport, David; Salomaa, Kai 6 2018 Site-directed insertion: decision problems, maximality and minimality. Zbl 1435.68152 Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 3 2018 Site-directed deletion. Zbl 1517.68180 Cho, Da-Jung; Han, Yo-Sub; Kim, Hwee; Salomaa, Kai 3 2018 Further closure properties of input-driven pushdown automata. Zbl 1435.68180 Okhotin, Alexander; Salomaa, Kai 2 2018 Cycle height of finite automata. Zbl 1435.68173 Keeler, Chris; Salomaa, Kai 1 2018 Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044 Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai 11 2017 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186 Okhotin, Alexander; Salomaa, Kai 10 2017 State complexity of permutation on finite languages over a binary alphabet. Zbl 1371.68145 Cho, Da-Jung; Goč, Daniel; Han, Yo-Sub; Ko, Sang-Ki; Palioudakis, Alexandros; Salomaa, Kai 9 2017 Outfix-guided insertion. Zbl 1382.68133 Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai 6 2017 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1489.68133 Okhotin, Alexander; Salomaa, Kai 6 2017 Branching measures and nearly acyclic NFAs. Zbl 1426.68147 Keeler, Chris; Salomaa, Kai 4 2017 Worst case branching and other measures of nondeterminism. Zbl 1371.68163 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2017 Descriptional complexity of error detection. Zbl 1396.68068 Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2017 The quotient operation on input-driven pushdown automata. Zbl 1426.68153 Okhotin, Alexander; Salomaa, Kai 3 2017 State complexity of prefix distance. Zbl 1371.68161 Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2017 State complexity of prefix distance of subregular languages. Zbl 1392.68219 Ng, Timothy; Rappaport, David; Salomaa, Kai 1 2017 Relative prefix distance between languages. Zbl 1494.68144 Ng, Timothy; Rappaport, David; Salomaa, Kai 1 2017 Consensus string problem for multiple regular languages. Zbl 1485.68143 Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 1 2017 State complexity of insertion. Zbl 1404.68069 Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 7 2016 State complexity of deletion and bipolar deletion. Zbl 1335.68121 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 5 2016 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317 Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 4 2016 Operational state complexity of unary NFAs with finite nondeterminism. Zbl 1332.68125 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2016 Pseudo-inversion: closure properties and decidability. Zbl 1415.68123 Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai 1 2016 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111 Okhotin, Alexander; Salomaa, Kai 9 2015 Quasi-distances and weighted finite automata. Zbl 1432.68239 Ng, Timothy; Rappaport, David; Salomaa, Kai 6 2015 State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096 Ng, Timothy; Rappaport, David; Salomaa, Kai 5 2015 State complexity of prefix distance. Zbl 1371.68160 Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2015 Generalizations of code languages with marginal errors. Zbl 1434.68255 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2015 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1327.68155 Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 2 2015 The state complexity of permutations on finite languages over binary alphabets. Zbl 1432.68241 Palioudakis, Alexandros; Cho, Da-Jung; Goč, Daniel; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2015 Duplications and pseudo-duplications. Zbl 1465.68081 Cho, Da-Jung; Han, Yo-Sub; Kim, Hwee; Palioudakis, Alexandros; Salomaa, Kai 2 2015 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224 Okhotin, Alexander; Salomaa, Kai 10 2014 Pseudo-inversion on formal languages. Zbl 1445.68121 Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai 4 2014 State complexity of inversion operations. Zbl 1332.68109 Cho, Da-Jung; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2014 Nondeterministic state complexity of proportional removals. Zbl 1320.68110 Goč, Daniel; Palioudakis, Alexandros; Salomaa, Kai 2 2014 Unary NFAs with limited nondeterminism. Zbl 1432.68242 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 2 2014 Top-down tree edit-distance of regular tree languages. Zbl 1407.68261 Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 1 2014 State complexity of unary language operations for NFAs with limited nondeterminism. Zbl 1332.68124 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2014 The edit-distance between a regular language and a context-free language. Zbl 1293.68187 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 15 2013 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1388.68168 Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 3 2013 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2013 Comparisons between measures of nondeterminism on finite automata. Zbl 1388.68177 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2013 Undecidability of state complexity. Zbl 1401.68167 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2013 Nondeterministic state complexity of proportional removals. Zbl 1304.68103 Goč, Daniel; Palioudakis, Alexandros; Salomaa, Kai 1 2013 State complexity of finite tree width NFAs. Zbl 1322.68126 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 9 2012 Cellular automaton based motion planning algorithms for mobile sensor networks. Zbl 1374.68309 Choudhury, Salimur; Salomaa, Kai; Akl, Selim G. 5 2012 State complexity and limited nondeterminism. Zbl 1304.68117 Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2012 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176 Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 3 2012 Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes. Zbl 1331.68139 Sears, David; Salomaa, Kai 3 2012 State complexity of the concatenation of regular tree languages. Zbl 1238.68079 Piao, Xiaoxue; Salomaa, Kai 3 2012 Computing the edit-distance between a regular language and a context-free language. Zbl 1370.68171 Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2012 State complexity of Kleene-star operations on trees. Zbl 1353.68171 Piao, Xiaoxue; Salomaa, Kai 2 2012 State-size hierarchy for finite-state complexity. Zbl 1283.68191 Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 2 2012 Finite state complexity. Zbl 1235.68088 Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 10 2011 Transition complexity of incomplete DFAs. Zbl 1230.68130 Gao, Yuan; Salomaa, Kai; Yu, Sheng 9 2011 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147 Okhotin, Alexander; Salomaa, Kai 6 2011 Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136 Salomaa, Kai 6 2011 Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235 Piao, Xiaoxue; Salomaa, Kai 6 2011 State trade-offs in unranked tree automata. Zbl 1341.68106 Piao, Xiaoxue; Salomaa, Kai 3 2011 Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172 Okhotin, Alexander; Salomaa, Kai 2 2011 Overlap-free languages and solid codes. Zbl 1222.68105 Han, Yo-Sub; Salomaa, Kai 1 2011 Nondeterministic state complexity for suffix-free regular languages. Zbl 1455.68091 Han, Yo-Sub; Salomaa, Kai 9 2010 Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141 Daley, M.; Domaratzki, M.; Salomaa, K. 7 2010 An improved cellular automata based algorithm for the 45-convex hull problem. Zbl 1182.68132 Clarridge, Adam G.; Salomaa, Kai 2 2010 Analysis of a cellular automaton model for car traffic with a slow-to-stop rule. Zbl 1207.68212 Clarridge, Adam; Salomaa, Kai 2 2010 Finite-state complexity and the size of transducers. Zbl 1455.68084 Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 1 2010 Operational state complexity of deterministic unranked tree automata. Zbl 1455.68095 Piao, Xiaoxue; Salomaa, Kai 1 2010 State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033 Han, Yo-Sub; Salomaa, Kai 34 2009 Operational state complexity of prefix-free regular languages. Zbl 1182.68105 Han, Yo-Sub; Salomaa, Kai; Wood, Derick 21 2009 Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534 Han, Yo-Sub; Salomaa, Kai; Wood, Derick 20 2009 Operational state complexity of nested word automata. Zbl 1176.68108 Piao, Xiaoxue; Salomaa, Kai 18 2009 Nondeterministic state complexity of nested word automata. Zbl 1173.68034 Han, Yo-Sub; Salomaa, Kai 16 2009 On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169 Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai 13 2009 Variants of codes and indecomposable languages. Zbl 1192.68423 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2009 State complexity of nested word automata. Zbl 1234.68238 Salomaa, Kai 2 2009 ...and 81 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 502 Authors 98 Salomaa, Kai T. 40 Han, Yo-Sub 36 Jirásková, Galina 33 Kutrib, Martin 33 Yu, Sheng 31 Salomaa, Arto Kustaa 29 Okhotin, Alexander 24 Ko, Sang-Ki 21 Brzozowski, Janusz Antoni 21 Holzer, Markus 20 Reidenbach, Daniel 20 Teh, Wen Chean 19 Kari, Lila 17 Hospodár, Michal 14 Subramanian, Kumbakonam Govindarajan 13 Malcher, Andreas 13 Ng, Timothy 12 Domaratzki, Michael 12 Schmid, Markus L. 12 Šebej, Juraj 11 Atanasiu, Adrian 11 Freydenberger, Dominik D. 11 Hoffmann, Stefan 11 Konstantinidis, Stavros 11 Vágvölgyi, Sándor 10 Gao, Yuan 9 Mahalingam, Kalpana 9 Manea, Florin 9 Pighizzini, Giovanni 9 Poovanandran, Ghajendran 9 Rappaport, David 9 Shallit, Jeffrey Outlaw 9 Wendlandt, Matthias 8 Bera, Somnath 8 Mateescu, Alexandru 8 McQuillan, Ian 8 Mlynárčik, Peter 8 Szykuła, Marek 8 Wood, Derick 7 Cho, Da-Jung 7 Nagy, Benedek 6 Caron, Pascal 6 Dassow, Jürgen 6 Karhumaki, Juhani 6 Kim, Sungmin 6 Luque, Jean-Gabriel 6 Nagar, Atulya K. 6 Patrou, Bruno 6 Piao, Xiaoxue 5 Bednárová, Zuzana 5 Câmpeanu, Cezar 5 Chatterjee, Kingshuk 5 Cui, Bo 5 Davies, Sylvie 5 Day, Joel D. 5 Fernau, Henning 5 Geffert, Viliam 5 Gruber, Hermann 5 Ibarra, Oscar H. 5 Jacquemard, Florent 5 Jirásek, Jozef jun. 5 Lange, Steffen 5 Olejár, Viktor 5 Otto, Friedrich 5 Palioudakis, Alexandros 5 Ray, Kumar Sankar 5 Schneider, Johannes C. 5 Smith, Taylor J. 4 Biegler, Franziska 4 Černý, Anton 4 Cheon, Hyunjoon 4 Eom, Hae-Sung 4 Jürgensen, Helmut 4 Keeler, Chris 4 Kopecki, Steffen 4 Masopust, Tomáš 4 Mathew, Lisa 4 Mereghetti, Carlo 4 Moreira, Nelma 4 Mráz, František 4 Palano, Beatrice 4 Reis, Rogério 4 Santean, Nicolae 4 Staiger, Ludwig 4 Szabari, Alexander 4 Thomas, Nobin 4 Zahedi, Mohammad Mehdi 4 Zeugmann, Thomas 3 Atanasiu, Radu-Florian 3 Bassino, Frédérique 3 Berglund, Martin 3 Daley, Mark 3 Fleischmann, Pamela 3 Ghorani, Maryam 3 Goč, Daniel 3 Godoy, Guillem 3 Harju, Tero 3 Jakobi, Sebastian 3 Jecker, Ismaël 3 Jordon, Liam ...and 402 more Authors all top 5 Cited in 56 Serials 175 Theoretical Computer Science 78 International Journal of Foundations of Computer Science 47 Information and Computation 21 Journal of Computer and System Sciences 15 Information Processing Letters 11 Acta Informatica 11 Theory of Computing Systems 8 RAIRO. Theoretical Informatics and Applications 7 Journal of Automata, Languages and Combinatorics 6 Discrete Applied Mathematics 6 International Journal of Computer Mathematics 6 RAIRO. Informatique Théorique et Applications 6 Natural Computing 5 Fuzzy Sets and Systems 4 Soft Computing 4 Fundamenta Informaticae 3 Formal Aspects of Computing 3 RAIRO. Theoretical Informatics and Applications 2 Algorithmica 2 International Journal of Approximate Reasoning 2 Discrete Mathematics and Theoretical Computer Science. DMTCS 2 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 2 Journal of Applied Mathematics and Computing 2 Logical Methods in Computer Science 2 Journal of Mathematics 1 Acta Mathematica Vietnamica 1 Automatica 1 Meccanica 1 Advances in Applied Mathematics 1 Bulletin of the Iranian Mathematical Society 1 Physica D 1 Acta Mathematicae Applicatae Sinica. English Series 1 Journal of Symbolic Computation 1 Journal of Automated Reasoning 1 Computational Geometry 1 International Journal of Algebra and Computation 1 Mathematical Structures in Computer Science 1 Discrete Event Dynamic Systems 1 Indagationes Mathematicae. New Series 1 Applicable Algebra in Engineering, Communication and Computing 1 The Australasian Journal of Combinatorics 1 Russian Mathematics 1 Journal of Logic, Language and Information 1 The Electronic Journal of Combinatorics 1 Computer Science Journal of Moldova 1 Journal of the ACM 1 Iranian Journal of Fuzzy Systems 1 Mathematics in Computer Science 1 Ars Mathematica Contemporanea 1 Algorithms 1 Journal of Applied Mathematics & Informatics 1 Statistics and Computing 1 Iranian Journal of Mathematical Sciences and Informatics 1 Computer Science Review 1 Journal of Logical and Algebraic Methods in Programming 1 Journal of Membrane Computing all top 5 Cited in 21 Fields 644 Computer science (68-XX) 21 Group theory and generalizations (20-XX) 20 Mathematical logic and foundations (03-XX) 18 Information and communication theory, circuits (94-XX) 17 Combinatorics (05-XX) 6 Number theory (11-XX) 6 Biology and other natural sciences (92-XX) 4 History and biography (01-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Dynamical systems and ergodic theory (37-XX) 3 Operations research, mathematical programming (90-XX) 2 Quantum theory (81-XX) 2 Systems theory; control (93-XX) 1 General and overarching topics; collections (00-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-XX) 1 Measure and integration (28-XX) 1 General topology (54-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Mechanics of deformable solids (74-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.