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: 235 Publications since 1984 7 Contributions as Editor Co-Authors: 57 Co-Authors with 220 Joint Publications 1,242 Co-Co-Authors all top 5 Co-Authors 22 single-authored 57 Yu, Sheng 55 Han, Yo-Sub 28 Ko, Sang-Ki 21 Ng, Timothy 17 Domaratzki, Michael 17 Salomaa, Arto Kustaa 15 Okhotin, Alexander 15 Palioudakis, Alexandros 14 Cho, Da-Jung 13 Rappaport, David 12 Piao, Xiaoxue 12 Wood, Derick 10 Akl, Selim G. 8 Keeler, Chris 7 Câmpeanu, Cezar 7 Smith, Taylor J. 6 Mateescu, Alexandru 5 Calude, Cristian S. 5 Goč, Daniel 4 Clarridge, Adam G. 4 Gao, Yuan 4 Kim, Hwee 4 Rozenberg, Grzegorz 3 Jiang, Tao 3 Jürgensen, Helmut 3 Kim, Sungmin 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 McQuillan, Ian 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 Holzer, Markus 1 Huerter, Sandra 1 Kari, Lila 1 Kinber, Efim B. 1 Kleijn, Jetty 1 Kouhestani, Bahram 1 Penttonen, Martti 1 Rahonis, George 1 Schofield, Paul 1 Stern, Manfred 1 Zhuang, Qingyu 1 Zu, Sheng all top 5 Serials 44 Theoretical Computer Science 22 International Journal of Foundations of Computer Science 11 Journal of Automata, Languages and Combinatorics 10 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 Journal of Cellular Automata all top 5 Fields 239 Computer science (68-XX) 7 General and overarching topics; collections (00-XX) 6 Mathematical logic and foundations (03-XX) 6 Biology and other natural sciences (92-XX) 3 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 171 Publications have been cited 1,137 times in 571 Documents Cited by ▼ Year ▼ The state complexities of some basic operations on regular languages. Zbl 0795.68112Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai 140 1994 A sharpening of the Parikh mapping. Zbl 1005.68092Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 66 2001 State complexity of combined operations. Zbl 1124.68056Salomaa, Arto; Salomaa, Kai; Yu, Sheng 39 2007 Decision problems for patterns. Zbl 0827.68066Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 36 1995 A formal study of practical regular expressions. Zbl 1101.68443Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 31 2003 State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033Han, Yo-Sub; Salomaa, Kai 31 2009 State complexity of basic operations on finite languages. Zbl 1050.68091Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 31 2001 Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 30 2002 Pattern languages with and without erasing. Zbl 0939.68690Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 27 1994 Deterministic tree pushdown automata and monadic tree rewriting systems. Zbl 0668.68084Salomaa, Kai 26 1988 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060Salomaa, Kai; Yu, Sheng 23 1997 Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534Han, Yo-Sub; Salomaa, Kai; Wood, Derick 18 2009 Operational state complexity of prefix-free regular languages. Zbl 1182.68105Han, Yo-Sub; Salomaa, Kai; Wood, Derick 18 2009 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040Gao, Yuan; Salomaa, Kai; Yu, Sheng 17 2008 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093Holzer, Markus; Salomaa, Kai; Yu, Sheng 17 2001 Operational state complexity of nested word automata. Zbl 1176.68108Piao, Xiaoxue; Salomaa, Kai 16 2009 On the state complexity of combined operations and their estimations. Zbl 1149.68397Salomaa, Kai; Zu, Sheng 15 2007 Additive distances and quasi-distances between words. Zbl 1258.68074Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 15 2002 Nondeterministic state complexity of nested word automata. Zbl 1173.68034Han, Yo-Sub; Salomaa, Kai 14 2009 State complexity of union and intersection of finite languages. Zbl 1155.68037Han, Yo-Sub; Salomaa, Kai 14 2008 The edit-distance between a regular language and a context-free language. Zbl 1293.68187Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 13 2013 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 0960.68611Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai 13 1995 On the existence of prime decompositions. Zbl 1111.68055Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 13 2007 Decidability of trajectory-based equations. Zbl 1079.68049Domaratzki, Michael; Salomaa, Kai 11 2005 Shuffle decompositions of regular languages. Zbl 1067.68085Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 9 2002 Inclusion is undecidable for pattern languages. Zbl 1422.68152Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 9 1993 State complexity of additive weighted finite automata. Zbl 1183.68354Salomaa, Kai; Schofield, Paul 9 2007 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224Okhotin, Alexander; Salomaa, Kai 8 2014 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186Okhotin, Alexander; Salomaa, Kai 8 2017 On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai 8 2009 Limited nondeterminism for pushdown automata. Zbl 1023.68621Salomaa, Kai; Yu, Sheng 8 1993 Measures of nondeterminism for pushdown automata. Zbl 0822.68070Salomaa, Kai; Yu, Sheng 8 1994 Transition complexity of incomplete DFAs. Zbl 1230.68130Gao, Yuan; Salomaa, Kai; Yu, Sheng 8 2011 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai 7 2017 Codes defined by multiple sets of trajectories. Zbl 1154.68066Domaratzki, Michael; Salomaa, Kai 7 2006 Transition complexity of language operations. Zbl 1143.68033Domaratzki, Michael; Salomaa, Kai 7 2007 Patterns. Zbl 1089.68059Salomaa, Kai 7 2004 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111Okhotin, Alexander; Salomaa, Kai 7 2015 Finite state complexity. Zbl 1235.68088Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 7 2011 Nondeterministic state complexity for suffix-free regular languages. Zbl 1455.68091Han, Yo-Sub; Salomaa, Kai 6 2010 State complexity of finite tree width NFAs. Zbl 1322.68126Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 6 2012 Quasi-distances and weighted finite automata. Zbl 1432.68239Ng, Timothy; Rappaport, David; Salomaa, Kai 6 2015 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039Salomaa, Kai; Yu, Sheng 6 1991 Descriptional complexity of nondeterministic finite automata. Zbl 1202.68239Salomaa, Kai 6 2007 Lower bounds for the transition complexity of NFAs. Zbl 1152.68028Domaratzki, Michael; Salomaa, Kai 6 2008 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147Okhotin, Alexander; Salomaa, Kai 6 2011 Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235Piao, Xiaoxue; Salomaa, Kai 6 2011 State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159Ng, Timothy; Rappaport, David; Salomaa, Kai 5 2018 State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096Ng, Timothy; Rappaport, David; Salomaa, Kai 5 2015 State complexity of insertion. Zbl 1404.68069Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 5 2016 State complexity of permutation on finite languages over a binary alphabet. Zbl 1371.68145Cho, Da-Jung; Goč, Daniel; Han, Yo-Sub; Ko, Sang-Ki; Palioudakis, Alexandros; Salomaa, Kai 5 2017 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1489.68133Okhotin, Alexander; Salomaa, Kai 5 2017 Prime decompositions of regular languages. Zbl 1227.68057Han, Yo-Sub; Salomaa, Kai; Wood, Derick 5 2006 Intercode regular languages. Zbl 1111.68056Han, Yo-Sub; Salomaa, Kai; Wood, Derick 5 2007 Primality types of instances of the Post correspondence problem. Zbl 0744.68083Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Synchronized tree automata. Zbl 0805.68084Salomaa, Kai 5 1994 Transducers and the decidability of independence in free monoids. Zbl 0938.68710Jürgensen, H.; Salomaa, K.; Yu, S. 5 1994 Alternating finite automata and star-free languages. Zbl 0944.68090Salomaa, K.; Yu, S. 5 2000 On fairness of many-dimensional trajectories. Zbl 0959.68068Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 5 2000 Cellular automaton based motion planning algorithms for mobile sensor networks. Zbl 1374.68309Choudhury, Salimur; Salomaa, Kai; Akl, Selim G. 5 2012 Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141Daley, M.; Domaratzki, M.; Salomaa, K. 5 2010 Outfix-guided insertion. Zbl 1382.68133Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai 4 2017 Restricted sets of trajectories and decidability of shuffle decompositions. Zbl 1080.68053Domaratzki, Michael; Salomaa, Kai 4 2005 State complexity of shuffle on trajectories. Zbl 1098.68068Domaratzki, Michael; Salomaa, Kai 4 2004 Decidability of the intercode property. Zbl 0824.68061Jürgensen, H.; Salomaa, K.; Yu, S. 4 1993 Structural equivalence and ET0L grammars. Zbl 0794.68093Salomaa, Kai; Wood, Derick; Yu, Sheng 4 1993 State complexity of deletion and bipolar deletion. Zbl 1335.68121Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 4 2016 Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136Salomaa, Kai 4 2011 Operational state complexity of unary NFAs with finite nondeterminism. Zbl 1332.68125Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2016 Pseudo-inversion on formal languages. Zbl 1445.68121Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai 3 2014 State complexity of prefix distance. Zbl 1371.68160Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2015 Generalizations of code languages with marginal errors. Zbl 1434.68255Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2015 Worst case branching and other measures of nondeterminism. Zbl 1371.68163Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2017 Yield-languages recognized by alternating tree recognizers. Zbl 0656.68087Salomaa, Kai 3 1988 Hierarchy of k-context-free languages. II. Zbl 0672.68039Salomaa, Kai 3 1989 Lower bounds for the transition complexity of NFAs (extended abstract). Zbl 1132.68441Domaratzki, Michael; Salomaa, Kai 3 2006 Iterated TGR languages: membership problem and effective closure properties. Zbl 1162.68473McQuillan, Ian; Salomaa, Kai; Daley, Mark 3 2006 On the existence of regular approximations. Zbl 1143.68032Cordy, Brendan; Salomaa, Kai 3 2007 Shuffle quotient and decompositions. Zbl 1073.68664Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 3 2002 Site-directed insertion: language equations and decision problems. Zbl 1435.68151Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 3 2019 On synchronization languages. Zbl 0843.68055Guo, L.; Salomaa, K.; Yu, S. 3 1996 Block-synchronization context-free grammars. Zbl 0867.68077Jürgensen, Helmut; Salomaa, Kai 3 1997 Pumping and pushdown machines. Zbl 0883.68093Salomaa, Kai; Wood, D.; Yu, Sheng 3 1994 Degrees of nondeterminism for pushdown automata. Zbl 0925.03175Salomaa, Kai; Yu, Sheng 3 1991 State complexity of basic operations on suffix-free regular languages. Zbl 1147.68559Han, Yo-Sub; Salomaa, Kai 3 2007 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 3 2016 Descriptional complexity of error detection. Zbl 1396.68068Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2017 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 3 2012 State complexity and limited nondeterminism. Zbl 1304.68117Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2012 State trade-offs in unranked tree automata. Zbl 1341.68106Piao, Xiaoxue; Salomaa, Kai 3 2011 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2013 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1388.68168Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 3 2013 Comparisons between measures of nondeterminism on finite automata. Zbl 1388.68177Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2013 State complexity of the concatenation of regular tree languages. Zbl 1238.68079Piao, Xiaoxue; Salomaa, Kai 3 2012 Decision problems for restricted variants of two-dimensional automata. Zbl 1434.68288Smith, Taylor J.; Salomaa, Kai 3 2019 Nondeterminism growth and state complexity. Zbl 1434.68268Keeler, Chris; Salomaa, Kai 3 2019 Alternating finite automata with limited universal branching. Zbl 1437.68099Keeler, Chris; Salomaa, Kai 2 2020 Structural properties of NFAs and growth rates of nondeterminism measures. Zbl 07488456Keeler, Chris; Salomaa, Kai 2 2022 Site-directed insertion: decision problems, maximality and minimality. Zbl 1435.68152Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 2 2018 Deciding path size of nondeterministic (and input-driven) pushdown automata. Zbl 07619402Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2023 Structural properties of NFAs and growth rates of nondeterminism measures. Zbl 07488456Keeler, Chris; Salomaa, Kai 2 2022 Nondeterministic state complexity of site-directed insertion. Zbl 07584602Lyon, Oliver A. S.; Salomaa, Kai 1 2022 Consensus string problem for multiple regular languages. Zbl 1497.68269Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 1 2021 Width measures of alternating finite automata. Zbl 07614744Keeler, C.; Salomaa, Kai 1 2021 Generalizations of code languages with marginal errors. Zbl 07726944Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 1 2021 Alternating finite automata with limited universal branching. Zbl 1437.68099Keeler, Chris; Salomaa, Kai 2 2020 Combining limited parallelism and nondeterminism in alternating finite automata. Zbl 07371292Keeler, Chris; Salomaa, Kai 2 2020 Recognition and complexity results for projection languages of two-dimensional automata. Zbl 07371301Smith, Taylor J.; Salomaa, Kai 1 2020 Site-directed insertion: language equations and decision problems. Zbl 1435.68151Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 3 2019 Decision problems for restricted variants of two-dimensional automata. Zbl 1434.68288Smith, Taylor J.; Salomaa, Kai 3 2019 Nondeterminism growth and state complexity. Zbl 1434.68268Keeler, Chris; Salomaa, Kai 3 2019 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1423.68262Okhotin, Alexander; Salomaa, Kai 2 2019 The relative edit-distance between two input-driven languages. Zbl 07117541Cheon, Hyunjoon; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2019 State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159Ng, Timothy; Rappaport, David; Salomaa, Kai 5 2018 Site-directed insertion: decision problems, maximality and minimality. Zbl 1435.68152Cho, Da-Jung; Han, Yo-Sub; Salomaa, Kai; Smith, Taylor J. 2 2018 Further closure properties of input-driven pushdown automata. Zbl 1435.68180Okhotin, Alexander; Salomaa, Kai 2 2018 Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050Kouhestani, Bahram; Rappaport, David; Salomaa, Kai 2 2018 Site-directed deletion. Zbl 1517.68180Cho, Da-Jung; Han, Yo-Sub; Kim, Hwee; Salomaa, Kai 2 2018 Cycle height of finite automata. Zbl 1435.68173Keeler, Chris; Salomaa, Kai 1 2018 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186Okhotin, Alexander; Salomaa, Kai 8 2017 Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai 7 2017 State complexity of permutation on finite languages over a binary alphabet. Zbl 1371.68145Cho, Da-Jung; Goč, Daniel; Han, Yo-Sub; Ko, Sang-Ki; Palioudakis, Alexandros; Salomaa, Kai 5 2017 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 1489.68133Okhotin, Alexander; Salomaa, Kai 5 2017 Outfix-guided insertion. Zbl 1382.68133Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai 4 2017 Worst case branching and other measures of nondeterminism. Zbl 1371.68163Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2017 Descriptional complexity of error detection. Zbl 1396.68068Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2017 State complexity of prefix distance. Zbl 1371.68161Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2017 Branching measures and nearly acyclic NFAs. Zbl 1426.68147Keeler, Chris; Salomaa, Kai 2 2017 The quotient operation on input-driven pushdown automata. Zbl 1426.68153Okhotin, Alexander; Salomaa, Kai 2 2017 State complexity of prefix distance of subregular languages. Zbl 1392.68219Ng, Timothy; Rappaport, David; Salomaa, Kai 1 2017 Consensus string problem for multiple regular languages. Zbl 1485.68143Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 1 2017 Relative prefix distance between languages. Zbl 1494.68144Ng, Timothy; Rappaport, David; Salomaa, Kai 1 2017 State complexity of insertion. Zbl 1404.68069Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 5 2016 State complexity of deletion and bipolar deletion. Zbl 1335.68121Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 4 2016 Operational state complexity of unary NFAs with finite nondeterminism. Zbl 1332.68125Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2016 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 3 2016 Pseudo-inversion: closure properties and decidability. Zbl 1415.68123Cho, 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.68111Okhotin, Alexander; Salomaa, Kai 7 2015 Quasi-distances and weighted finite automata. Zbl 1432.68239Ng, Timothy; Rappaport, David; Salomaa, Kai 6 2015 State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096Ng, Timothy; Rappaport, David; Salomaa, Kai 5 2015 State complexity of prefix distance. Zbl 1371.68160Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2015 Generalizations of code languages with marginal errors. Zbl 1434.68255Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2015 Duplications and pseudo-duplications. Zbl 1465.68081Cho, Da-Jung; Han, Yo-Sub; Kim, Hwee; Palioudakis, Alexandros; Salomaa, Kai 2 2015 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1327.68155Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 2 2015 The state complexity of permutations on finite languages over binary alphabets. Zbl 1432.68241Palioudakis, Alexandros; Cho, Da-Jung; Goč, Daniel; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2015 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224Okhotin, Alexander; Salomaa, Kai 8 2014 Pseudo-inversion on formal languages. Zbl 1445.68121Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai 3 2014 State complexity of inversion operations. Zbl 1332.68109Cho, Da-Jung; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2014 Unary NFAs with limited nondeterminism. Zbl 1432.68242Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 2 2014 Nondeterministic state complexity of proportional removals. Zbl 1320.68110Goč, Daniel; Palioudakis, Alexandros; Salomaa, Kai 1 2014 State complexity of unary language operations for NFAs with limited nondeterminism. Zbl 1332.68124Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2014 Top-down tree edit-distance of regular tree languages. Zbl 1407.68261Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 1 2014 The edit-distance between a regular language and a context-free language. Zbl 1293.68187Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 13 2013 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 3 2013 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1388.68168Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 3 2013 Comparisons between measures of nondeterminism on finite automata. Zbl 1388.68177Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2013 Nondeterministic state complexity of proportional removals. Zbl 1304.68103Goč, Daniel; Palioudakis, Alexandros; Salomaa, Kai 1 2013 Undecidability of state complexity. Zbl 1401.68167Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 2013 State complexity of finite tree width NFAs. Zbl 1322.68126Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 6 2012 Cellular automaton based motion planning algorithms for mobile sensor networks. Zbl 1374.68309Choudhury, Salimur; Salomaa, Kai; Akl, Selim G. 5 2012 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 3 2012 State complexity and limited nondeterminism. Zbl 1304.68117Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 3 2012 State complexity of the concatenation of regular tree languages. Zbl 1238.68079Piao, Xiaoxue; Salomaa, Kai 3 2012 Computing the edit-distance between a regular language and a context-free language. Zbl 1370.68171Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2012 State complexity of Kleene-star operations on trees. Zbl 1353.68171Piao, Xiaoxue; Salomaa, Kai 2 2012 State-size hierarchy for finite-state complexity. Zbl 1283.68191Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 2 2012 Transition complexity of incomplete DFAs. Zbl 1230.68130Gao, Yuan; Salomaa, Kai; Yu, Sheng 8 2011 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 Finite state complexity. Zbl 1235.68088Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 7 2011 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147Okhotin, Alexander; Salomaa, Kai 6 2011 Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235Piao, Xiaoxue; Salomaa, Kai 6 2011 Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136Salomaa, Kai 4 2011 State trade-offs in unranked tree automata. Zbl 1341.68106Piao, Xiaoxue; Salomaa, Kai 3 2011 Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172Okhotin, Alexander; Salomaa, Kai 2 2011 Overlap-free languages and solid codes. Zbl 1222.68105Han, Yo-Sub; Salomaa, Kai 1 2011 Nondeterministic state complexity for suffix-free regular languages. Zbl 1455.68091Han, Yo-Sub; Salomaa, Kai 6 2010 Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141Daley, M.; Domaratzki, M.; Salomaa, K. 5 2010 Analysis of a cellular automaton model for car traffic with a slow-to-stop rule. Zbl 1207.68212Clarridge, Adam; Salomaa, Kai 2 2010 An improved cellular automata based algorithm for the 45-convex hull problem. Zbl 1182.68132Clarridge, Adam G.; Salomaa, Kai 2 2010 Finite-state complexity and the size of transducers. Zbl 1455.68084Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 1 2010 Operational state complexity of deterministic unranked tree automata. Zbl 1455.68095Piao, Xiaoxue; Salomaa, Kai 1 2010 State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033Han, Yo-Sub; Salomaa, Kai 31 2009 Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534Han, Yo-Sub; Salomaa, Kai; Wood, Derick 18 2009 Operational state complexity of prefix-free regular languages. Zbl 1182.68105Han, Yo-Sub; Salomaa, Kai; Wood, Derick 18 2009 Operational state complexity of nested word automata. Zbl 1176.68108Piao, Xiaoxue; Salomaa, Kai 16 2009 Nondeterministic state complexity of nested word automata. Zbl 1173.68034Han, Yo-Sub; Salomaa, Kai 14 2009 On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai 8 2009 State complexity of nested word automata. Zbl 1234.68238Salomaa, Kai 2 2009 State complexity of combined operations for prefix-free regular languages. Zbl 1234.68210Han, Yo-Sub; Salomaa, Kai; Yu, Sheng 2 2009 Variants of codes and indecomposable languages. Zbl 1192.68423Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2009 A cryptosystem based on the composition of reversible cellular automata. Zbl 1234.94036Clarridge, Adam; Salomaa, Kai 1 2009 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040Gao, Yuan; Salomaa, Kai; Yu, Sheng 17 2008 State complexity of union and intersection of finite languages. Zbl 1155.68037Han, Yo-Sub; Salomaa, Kai 14 2008 Lower bounds for the transition complexity of NFAs. Zbl 1152.68028Domaratzki, Michael; Salomaa, Kai 6 2008 Length codes, products of languages and primality. Zbl 1156.68464Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 2008 State complexity of combined operations. Zbl 1124.68056Salomaa, Arto; Salomaa, Kai; Yu, Sheng 39 2007 On the state complexity of combined operations and their estimations. Zbl 1149.68397Salomaa, Kai; Zu, Sheng 15 2007 On the existence of prime decompositions. Zbl 1111.68055Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 13 2007 State complexity of additive weighted finite automata. Zbl 1183.68354Salomaa, Kai; Schofield, Paul 9 2007 ...and 71 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 437 Authors 88 Salomaa, Kai T. 35 Han, Yo-Sub 31 Jirásková, Galina 31 Kutrib, Martin 31 Yu, Sheng 28 Salomaa, Arto Kustaa 26 Okhotin, Alexander 22 Ko, Sang-Ki 20 Holzer, Markus 20 Reidenbach, Daniel 19 Brzozowski, Janusz Antoni 18 Kari, Lila 18 Teh, Wen Chean 14 Subramanian, Kumbakonam Govindarajan 13 Hospodár, Michal 13 Ng, Timothy 12 Domaratzki, Michael 12 Malcher, Andreas 11 Freydenberger, Dominik D. 11 Schmid, Markus L. 11 Šebej, Juraj 11 Vágvölgyi, Sándor 10 Atanasiu, Adrian 10 Gao, Yuan 10 Konstantinidis, Stavros 9 Wendlandt, Matthias 8 Bera, Somnath 8 Mahalingam, Kalpana 8 Mateescu, Alexandru 8 McQuillan, Ian 8 Rappaport, David 8 Shallit, Jeffrey Outlaw 7 Mlynárčik, Peter 7 Pighizzini, Giovanni 7 Poovanandran, Ghajendran 7 Szykuła, Marek 7 Wood, Derick 6 Cho, Da-Jung 6 Dassow, Jürgen 6 Karhumaki, Juhani 6 Luque, Jean-Gabriel 6 Nagar, Atulya K. 6 Piao, Xiaoxue 5 Bednárová, Zuzana 5 Câmpeanu, Cezar 5 Caron, Pascal 5 Cui, Bo 5 Day, Joel D. 5 Fernau, Henning 5 Geffert, Viliam 5 Gruber, Hermann 5 Hoffmann, Stefan 5 Ibarra, Oscar H. 5 Jacquemard, Florent 5 Jirásek, Jozef jun. 5 Lange, Steffen 5 Manea, Florin 5 Olejár, Viktor 5 Otto, Friedrich 5 Palioudakis, Alexandros 5 Patrou, Bruno 5 Schneider, Johannes C. 4 Biegler, Franziska 4 Černý, Anton 4 Chatterjee, Kingshuk 4 Eom, Hae-Sung 4 Jürgensen, Helmut 4 Kopecki, Steffen 4 Masopust, Tomáš 4 Mathew, Lisa 4 Mereghetti, Carlo 4 Mráz, František 4 Palano, Beatrice 4 Ray, Kumar Sankar 4 Santean, Nicolae 4 Staiger, Ludwig 4 Szabari, Alexander 4 Thomas, Nobin 4 Zeugmann, Thomas 3 Atanasiu, Radu-Florian 3 Bassino, Frédérique 3 Berglund, Martin 3 Daley, Mark 3 Davies, Sylvie 3 Ghorani, Maryam 3 Goč, Daniel 3 Godoy, Guillem 3 Harju, Tero 3 Jakobi, Sebastian 3 Keeler, Chris 3 Kim, Sungmin 3 Kunc, Michal 3 Lipponen, Marjo 3 Lyon, Oliver A. S. 3 Martín-Vide, Carlos 3 Mercaş, Robert George 3 Mitrana, Victor 3 Moreira, Nelma 3 Nagy, Benedek 3 Nicaud, Cyril ...and 337 more Authors all top 5 Cited in 50 Serials 164 Theoretical Computer Science 77 International Journal of Foundations of Computer Science 42 Information and Computation 20 Journal of Computer and System Sciences 15 Information Processing Letters 11 Acta Informatica 9 Theory of Computing Systems 8 RAIRO. Theoretical Informatics and Applications 6 Discrete Applied Mathematics 6 International Journal of Computer Mathematics 6 RAIRO. Informatique Théorique et Applications 4 Journal of Automata, Languages and Combinatorics 4 Soft Computing 4 Natural Computing 3 Fuzzy Sets and Systems 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 Fundamenta Informaticae 2 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 2 Journal of Applied Mathematics and Computing 2 Journal of Mathematics 1 Acta Mathematica Vietnamica 1 Meccanica 1 Advances in Applied Mathematics 1 Bulletin of the Iranian Mathematical Society 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 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 Logical Methods in Computer Science 1 Ars Mathematica Contemporanea 1 Algorithms 1 Statistics and Computing 1 Computer Science Review 1 Journal of Logical and Algebraic Methods in Programming all top 5 Cited in 18 Fields 565 Computer science (68-XX) 21 Mathematical logic and foundations (03-XX) 17 Group theory and generalizations (20-XX) 15 Combinatorics (05-XX) 15 Information and communication theory, circuits (94-XX) 4 History and biography (01-XX) 4 Number theory (11-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Biology and other natural sciences (92-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Operations research, mathematical programming (90-XX) 1 General and overarching topics; collections (00-XX) 1 Category theory; homological algebra (18-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Quantum theory (81-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Systems theory; control (93-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.