Edit Profile Salomaa, Kai T. Compute Distance To: Compute Author ID: salomaa.kai-t Published as: Salomaa, K.; Salomaa, Kai; Salomaa, Kai T. External Links: MGP · Wikidata · dblp · GND Documents Indexed: 222 Publications since 1984, including 5 Books all top 5 Co-Authors 20 single-authored 56 Yu, Sheng 48 Han, Yo-Sub 21 Ko, Sang-Ki 19 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 11 Wood, Derick 10 Akl, Selim G. 7 Câmpeanu, Cezar 6 Mateescu, Alexandru 5 Calude, Cristian S. 5 Goč, Daniel 5 Keeler, Chris 4 Clarridge, Adam G. 4 Gao, Yuan 4 Kim, Hwee 4 Rozenberg, Grzegorz 3 Jiang, Tao 3 Jürgensen, Helmut 3 Roblot, Tania K. 3 Smith, Taylor J. 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 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 Guo, Longxiang 1 Holzer, Markus 1 Huerter, Sandra 1 Kari, Lila 1 Kinber, Efim B. 1 Kleijn, H. C. M. 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 39 Theoretical Computer Science 21 International Journal of Foundations of Computer Science 10 Journal of Automata, Languages and Combinatorics 10 Fundamenta Informaticae 5 Journal of Computer and System Sciences 4 Acta Cybernetica 4 Information and Computation 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 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 219 Computer science (68-XX) 7 General and overarching topics; collections (00-XX) 6 Biology and other natural sciences (92-XX) 5 Mathematical logic and foundations (03-XX) 3 History and biography (01-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) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH 135 Publications have been cited 828 times in 429 Documents Cited by ▼ Year ▼ The state complexities of some basic operations on regular languages. Zbl 0795.68112Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai 107 1994 A sharpening of the Parikh mapping. Zbl 1005.68092Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 53 2001 State complexity of combined operations. Zbl 1124.68056Salomaa, Arto; Salomaa, Kai; Yu, Sheng 35 2007 Decision problems for patterns. Zbl 0827.68066Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 32 1995 A formal study of practical regular expressions. Zbl 1101.68443Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 27 2003 State complexity of basic operations on finite languages. Zbl 1050.68091Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 24 2001 Pattern languages with and without erasing. Zbl 0939.68690Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 24 1994 State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033Han, Yo-Sub; Salomaa, Kai 23 2009 Deterministic tree pushdown automata and monadic tree rewriting systems. Zbl 0668.68084Salomaa, Kai 23 1988 Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 22 2002 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060Salomaa, Kai; Yu, Sheng 17 1997 Operational state complexity of nested word automata. Zbl 1176.68108Piao, Xiaoxue; Salomaa, Kai 15 2009 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040Gao, Yuan; Salomaa, Kai; Yu, Sheng 15 2008 On the state complexity of combined operations and their estimations. Zbl 1149.68397Salomaa, Kai; Zu, Sheng 15 2007 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093Holzer, Markus; Salomaa, Kai; Yu, Sheng 14 2001 Nondeterministic state complexity of nested word automata. Zbl 1173.68034Han, Yo-Sub; Salomaa, Kai 13 2009 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 0960.68611Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai 13 1995 Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534Han, Yo-Sub; Salomaa, Kai; Wood, Derick 12 2009 Operational state complexity of prefix-free regular languages. Zbl 1182.68105Han, Yo-Sub; Salomaa, Kai; Wood, Derick 11 2009 State complexity of union and intersection of finite languages. Zbl 1155.68037Han, Yo-Sub; Salomaa, Kai 10 2008 On the existence of prime decompositions. Zbl 1111.68055Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 10 2007 Decidability of trajectory-based equations. Zbl 1079.68049Domaratzki, Michael; Salomaa, Kai 9 2005 Additive distances and quasi-distances between words. Zbl 1258.68074Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 9 2002 The edit-distance between a regular language and a context-free language. Zbl 1293.68187Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 8 2013 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 Patterns. Zbl 1089.68059Salomaa, Kai 7 2004 Inclusion is undecidable for pattern languages. Zbl 1422.68152Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 7 1993 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186Okhotin, Alexander; Salomaa, Kai 6 2017 Transition complexity of incomplete DFAs. Zbl 1230.68130Gao, Yuan; Salomaa, Kai; Yu, Sheng 6 2011 Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235Piao, Xiaoxue; Salomaa, Kai 6 2011 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147Okhotin, Alexander; Salomaa, Kai 6 2011 On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai 6 2009 State complexity of additive weighted finite automata. Zbl 1183.68354Salomaa, Kai; Schofield, Paul 6 2007 Codes defined by multiple sets of trajectories. Zbl 1154.68066Domaratzki, Michael; Salomaa, Kai 6 2006 Shuffle decompositions of regular languages. Zbl 1067.68085Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 6 2002 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111Okhotin, Alexander; Salomaa, Kai 5 2015 Lower bounds for the transition complexity of NFAs. Zbl 1152.68028Domaratzki, Michael; Salomaa, Kai 5 2008 Transition complexity of language operations. Zbl 1143.68033Domaratzki, Michael; Salomaa, Kai 5 2007 Descriptional complexity of nondeterministic finite automata. Zbl 1202.68239Salomaa, Kai 5 2007 Transducers and the decidability of independence in free monoids. Zbl 0938.68710Jürgensen, H.; Salomaa, K.; Yu, S. 5 1994 Measures of nondeterminism for pushdown automata. Zbl 0822.68070Salomaa, Kai; Yu, Sheng 5 1994 Limited nondeterminism for pushdown automata. Zbl 1023.68621Salomaa, Kai; Yu, Sheng 5 1993 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039Salomaa, Kai; Yu, Sheng 5 1991 Primality types of instances of the Post correspondence problem. Zbl 0744.68083Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Quasi-distances and weighted finite automata. Zbl 1432.68239Ng, Timothy; Rappaport, David; Salomaa, Kai 4 2015 Finite state complexity. Zbl 1235.68088Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 4 2011 Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136Salomaa, Kai 4 2011 State complexity of shuffle on trajectories. Zbl 1098.68068Domaratzki, Michael; Salomaa, Kai 4 2004 On fairness of many-dimensional trajectories. Zbl 0959.68068Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 4 2000 Synchronized tree automata. Zbl 0805.68084Salomaa, Kai 4 1994 Decidability of the intercode property. Zbl 0824.68061Jürgensen, H.; Salomaa, K.; Yu, S. 4 1993 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 06763511Okhotin, Alexander; Salomaa, Kai 3 2017 State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2015 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 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224Okhotin, Alexander; Salomaa, Kai 3 2014 State complexity of the concatenation of regular tree languages. Zbl 1238.68079Piao, Xiaoxue; Salomaa, Kai 3 2012 State trade-offs in unranked tree automata. Zbl 1341.68106Piao, Xiaoxue; Salomaa, Kai 3 2011 Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141Daley, M.; Domaratzki, M.; Salomaa, K. 3 2010 Prime decompositions of regular languages. Zbl 1227.68057Han, Yo-Sub; Salomaa, Kai; Wood, Derick 3 2006 Restricted sets of trajectories and decidability of shuffle decompositions. Zbl 1080.68053Domaratzki, Michael; Salomaa, Kai 3 2005 Alternating finite automata and star-free languages. Zbl 0944.68090Salomaa, K.; Yu, S. 3 2000 Block-synchronization context-free grammars. Zbl 0867.68077Jürgensen, Helmut; Salomaa, Kai 3 1997 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 1044.68660Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 3 1996 On synchronization languages. Zbl 0843.68055Guo, L.; Salomaa, K.; Yu, S. 3 1996 Structural equivalence and ET0L grammars. Zbl 0794.68093Salomaa, Kai; Wood, Derick; Yu, Sheng 3 1993 State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2018 Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050Kouhestani, Bahram; Rappaport, David; Salomaa, Kai 2 2018 Descriptional complexity of error detection. Zbl 1396.68068Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2017 The quotient operation on input-driven pushdown automata. Zbl 1426.68153Okhotin, Alexander; Salomaa, Kai 2 2017 State complexity of insertion. Zbl 1404.68069Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 2 2016 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 2 2016 State complexity of deletion and bipolar deletion. Zbl 1335.68121Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2016 State complexity of prefix distance. Zbl 1371.68160Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2015 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2013 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 2 2012 State-size hierarchy for finite-state complexity. Zbl 1283.68191Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 2 2012 State complexity of Kleene-star operations on trees. Zbl 1353.68171Piao, Xiaoxue; Salomaa, Kai 2 2012 Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172Okhotin, Alexander; Salomaa, Kai 2 2011 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 Variants of codes and indecomposable languages. Zbl 1192.68423Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2009 State complexity of combined operations for prefix-free regular languages. Zbl 1234.68210Han, Yo-Sub; Salomaa, Kai; Yu, Sheng 2 2009 State complexity of nested word automata. Zbl 1234.68238Salomaa, Kai 2 2009 State complexity of basic operations on suffix-free regular languages. Zbl 1147.68559Han, Yo-Sub; Salomaa, Kai 2 2007 On the existence of regular approximations. Zbl 1143.68032Cordy, Brendan; Salomaa, Kai 2 2007 Intercode regular languages. Zbl 1111.68056Han, Yo-Sub; Salomaa, Kai; Wood, Derick 2 2007 Iterated TGR languages: membership problem and effective closure properties. Zbl 1162.68473McQuillan, Ian; Salomaa, Kai; Daley, Mark 2 2006 Lower bounds for the transition complexity of NFAs (extended abstract). Zbl 1132.68441Domaratzki, Michael; Salomaa, Kai 2 2006 Decidability of trajectory-based equations. Zbl 1097.68057Domaratzki, Michael; Salomaa, Kai 2 2004 Shuffle quotient and decompositions. Zbl 1073.68664Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 2 2002 Synchronization expressions with extended join operation. Zbl 0912.68108Salomaa, Kai; Yu, Sheng 2 1998 Complexity of E0L structural equivalence. Zbl 0881.68070Salomaa, Kai; Wood, Derick; Yu, Sheng 2 1995 Pumping and pushdown machines. Zbl 0883.68093Salomaa, Kai; Wood, D.; Yu, Sheng 2 1994 Degrees of nondeterminism for pushdown automata. Zbl 0925.03175Salomaa, Kai; Yu, Sheng 2 1991 Hierarchy of k-context-free languages. II. Zbl 0672.68039Salomaa, Kai 2 1989 A pumping result for 2-context-free languages. Zbl 0662.68077Salomaa, Kai 2 1988 Yield-languages recognized by alternating tree recognizers. Zbl 0656.68087Salomaa, Kai 2 1988 State complexity of prefix distance of subregular languages. Zbl 1392.68219Ng, Timothy; Rappaport, David; Salomaa, Kai 1 2017 Outfix-guided insertion. Zbl 1382.68133Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai 1 2017 Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai 1 2017 State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2018 Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050Kouhestani, Bahram; Rappaport, David; Salomaa, Kai 2 2018 State complexity of operations on input-driven pushdown automata. Zbl 1370.68186Okhotin, Alexander; Salomaa, Kai 6 2017 Edit distance neighbourhoods of input-driven pushdown automata. Zbl 06763511Okhotin, Alexander; Salomaa, Kai 3 2017 Descriptional complexity of error detection. Zbl 1396.68068Ng, Timothy; Rappaport, David; 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 Outfix-guided insertion. Zbl 1382.68133Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai 1 2017 Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai 1 2017 State complexity of insertion. Zbl 1404.68069Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai 2 2016 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai 2 2016 State complexity of deletion and bipolar deletion. Zbl 1335.68121Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2016 Operational state complexity of unary NFAs with finite nondeterminism. Zbl 1332.68125Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2016 Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111Okhotin, Alexander; Salomaa, Kai 5 2015 Quasi-distances and weighted finite automata. Zbl 1432.68239Ng, Timothy; Rappaport, David; Salomaa, Kai 4 2015 State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096Ng, Timothy; Rappaport, David; Salomaa, Kai 3 2015 State complexity of prefix distance. Zbl 1371.68160Ng, Timothy; Rappaport, David; Salomaa, Kai 2 2015 Generalizations of code languages with marginal errors. Zbl 1434.68255Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2015 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1327.68155Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 1 2015 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 Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224Okhotin, Alexander; Salomaa, Kai 3 2014 Nondeterministic state complexity of proportional removals. Zbl 1320.68110Goč, Daniel; Palioudakis, Alexandros; Salomaa, Kai 1 2014 Unary NFAs with limited nondeterminism. Zbl 1432.68242Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2014 State complexity of unary language operations for NFAs with limited nondeterminism. Zbl 1332.68124Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2014 State complexity of inversion operations. Zbl 1332.68109Cho, Da-Jung; Han, Yo-Sub; Ko, Sang-Ki; 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 8 2013 Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 2 2013 Undecidability of state complexity. Zbl 1401.68167Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 2013 Comparisons between measures of nondeterminism on finite automata. Zbl 1388.68177Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2013 State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1388.68168Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai 1 2013 State complexity of the concatenation of regular tree languages. Zbl 1238.68079Piao, Xiaoxue; Salomaa, Kai 3 2012 Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai 2 2012 State-size hierarchy for finite-state complexity. Zbl 1283.68191Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 2 2012 State complexity of Kleene-star operations on trees. Zbl 1353.68171Piao, Xiaoxue; Salomaa, Kai 2 2012 State complexity of finite tree width NFAs. Zbl 1322.68126Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2012 Cellular automaton based motion planning algorithms for mobile sensor networks. Zbl 1374.68309Choudhury, Salimur; Salomaa, Kai; Akl, Selim G. 1 2012 State complexity and limited nondeterminism. Zbl 1304.68117Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. 1 2012 Computing the edit-distance between a regular language and a context-free language. Zbl 1370.68171Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai 1 2012 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 Transition complexity of incomplete DFAs. Zbl 1230.68130Gao, Yuan; Salomaa, Kai; Yu, Sheng 6 2011 Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235Piao, Xiaoxue; Salomaa, Kai 6 2011 State complexity of operations on input-driven pushdown automata. Zbl 1343.68147Okhotin, Alexander; Salomaa, Kai 6 2011 Finite state complexity. Zbl 1235.68088Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K. 4 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 Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141Daley, M.; Domaratzki, M.; Salomaa, K. 3 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 State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033Han, Yo-Sub; Salomaa, Kai 23 2009 Operational state complexity of nested word automata. Zbl 1176.68108Piao, Xiaoxue; Salomaa, Kai 15 2009 Nondeterministic state complexity of nested word automata. Zbl 1173.68034Han, Yo-Sub; Salomaa, Kai 13 2009 Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534Han, Yo-Sub; Salomaa, Kai; Wood, Derick 12 2009 Operational state complexity of prefix-free regular languages. Zbl 1182.68105Han, Yo-Sub; Salomaa, Kai; Wood, Derick 11 2009 On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai 6 2009 Variants of codes and indecomposable languages. Zbl 1192.68423Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2009 State complexity of combined operations for prefix-free regular languages. Zbl 1234.68210Han, Yo-Sub; Salomaa, Kai; Yu, Sheng 2 2009 State complexity of nested word automata. Zbl 1234.68238Salomaa, Kai 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 15 2008 State complexity of union and intersection of finite languages. Zbl 1155.68037Han, Yo-Sub; Salomaa, Kai 10 2008 Lower bounds for the transition complexity of NFAs. Zbl 1152.68028Domaratzki, Michael; Salomaa, Kai 5 2008 State complexity of combined operations. Zbl 1124.68056Salomaa, Arto; Salomaa, Kai; Yu, Sheng 35 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 10 2007 State complexity of additive weighted finite automata. Zbl 1183.68354Salomaa, Kai; Schofield, Paul 6 2007 Transition complexity of language operations. Zbl 1143.68033Domaratzki, Michael; Salomaa, Kai 5 2007 Descriptional complexity of nondeterministic finite automata. Zbl 1202.68239Salomaa, Kai 5 2007 State complexity of basic operations on suffix-free regular languages. Zbl 1147.68559Han, Yo-Sub; Salomaa, Kai 2 2007 On the existence of regular approximations. Zbl 1143.68032Cordy, Brendan; Salomaa, Kai 2 2007 Intercode regular languages. Zbl 1111.68056Han, Yo-Sub; Salomaa, Kai; Wood, Derick 2 2007 Deterministic caterpillar expressions. Zbl 1139.68374Salomaa, Kai; Yu, Sheng; Zan, Jinfeng 1 2007 An infinite hierarchy induced by depth synchronization. Zbl 1143.68026Biegler, Franziska; McQuillan, Ian; Salomaa, Kai 1 2007 State complexity of union and intersection of finite languages. Zbl 1202.68227Han, Yo-Sub; Salomaa, Kai 1 2007 Codes defined by multiple sets of trajectories. Zbl 1154.68066Domaratzki, Michael; Salomaa, Kai 6 2006 Prime decompositions of regular languages. Zbl 1227.68057Han, Yo-Sub; Salomaa, Kai; Wood, Derick 3 2006 Iterated TGR languages: membership problem and effective closure properties. Zbl 1162.68473McQuillan, Ian; Salomaa, Kai; Daley, Mark 2 2006 Lower bounds for the transition complexity of NFAs (extended abstract). Zbl 1132.68441Domaratzki, Michael; Salomaa, Kai 2 2006 Interpreted trajectories. Zbl 1157.68380Domaratzki, Michael; Rozenberg, Grzegorz; Salomaa, Kai 1 2006 Decidability of trajectory-based equations. Zbl 1079.68049Domaratzki, Michael; Salomaa, Kai 9 2005 Restricted sets of trajectories and decidability of shuffle decompositions. Zbl 1080.68053Domaratzki, Michael; Salomaa, Kai 3 2005 Patterns. Zbl 1089.68059Salomaa, Kai 7 2004 State complexity of shuffle on trajectories. Zbl 1098.68068Domaratzki, Michael; Salomaa, Kai 4 2004 Decidability of trajectory-based equations. Zbl 1097.68057Domaratzki, Michael; Salomaa, Kai 2 2004 A formal study of practical regular expressions. Zbl 1101.68443Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 27 2003 Deletion on trajectories and commutative closure. Zbl 1040.68053Domaratzki, Michael; Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 1 2003 Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 22 2002 Additive distances and quasi-distances between words. Zbl 1258.68074Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 9 2002 Shuffle decompositions of regular languages. Zbl 1067.68085Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 6 2002 Shuffle quotient and decompositions. Zbl 1073.68664Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S. 2 2002 One-visit caterpillar tree automata. Zbl 1012.68102Okhotin, Alexander; Salomaa, Kai; Domaratzki, Michael 1 2002 A sharpening of the Parikh mapping. Zbl 1005.68092Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 53 2001 State complexity of basic operations on finite languages. Zbl 1050.68091Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 24 2001 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093Holzer, Markus; Salomaa, Kai; Yu, Sheng 14 2001 Metric lexical analysis. Zbl 1050.68090Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 1 2001 On fairness of many-dimensional trajectories. Zbl 0959.68068Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 4 2000 Alternating finite automata and star-free languages. Zbl 0944.68090Salomaa, K.; Yu, S. 3 2000 Efficient implementation of regular languages using reversed alternating finite automata. Zbl 0951.68061Salomaa, K.; Wu, X.; Yu, S. 1 2000 Synchronization expressions and languages. Zbl 0960.68097Salomaa, Kai; Yu, Sheng 1 1999 Synchronization expressions with extended join operation. Zbl 0912.68108Salomaa, Kai; Yu, Sheng 2 1998 ...and 35 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 358 Authors 64 Salomaa, Kai T. 29 Yu, Sheng 28 Jirásková, Galina 28 Salomaa, Arto Kustaa 23 Kutrib, Martin 22 Han, Yo-Sub 21 Okhotin, Alexander 16 Brzozowski, Janusz Antoni 16 Holzer, Markus 16 Kari, Lila 15 Teh, Wen Chean 14 Reidenbach, Daniel 12 Ko, Sang-Ki 11 Domaratzki, Michael 11 Schmid, Markus L. 10 Freydenberger, Dominik D. 10 Gao, Yuan 10 Subramanian, Kumbakonam Govindarajan 9 Malcher, Andreas 9 Vágvölgyi, Sándor 8 Atanasiu, Adrian 8 Jirásek, Jozef jun. 8 Mateescu, Alexandru 8 Ng, Timothy 8 Šebej, Juraj 7 Bera, Somnath 7 Konstantinidis, Stavros 7 Mahalingam, Kalpana 6 Karhumaki, Juhani 6 McQuillan, Ian 6 Piao, Xiaoxue 6 Poovanandran, Ghajendran 6 Rappaport, David 6 Shallit, Jeffrey O. 6 Wood, Derick 5 Cui, Bo 5 Fernau, Henning 5 Hospodár, Michal 5 Jacquemard, Florent 5 Manea, Florin 5 Mlynárčik, Peter 5 Pighizzini, Giovanni 5 Schneider, Johannes C. 5 Wendlandt, Matthias 4 Bednárová, Zuzana 4 Biegler, Franziska 4 Câmpeanu, Cezar 4 Černý, Anton 4 Cho, Da-Jung 4 Eom, Hae-Sung 4 Geffert, Viliam 4 Lange, Steffen 4 Mereghetti, Carlo 4 Nagar, Atulya K. 4 Palano, Beatrice 4 Santean, Nicolae 4 Szykuła, Marek 3 Atanasiu, Radu-Florian 3 Caron, Pascal 3 Chatterjee, Kingshuk 3 Daley, Mark 3 Dassow, Jürgen 3 Davies, Sylvie 3 Day, Joel D. 3 Godoy, Guillem 3 Gruber, Hermann 3 Ibarra, Oscar H. 3 Jürgensen, Helmut 3 Kopecki, Steffen 3 Lipponen, Marjo 3 Liu, Guangwu 3 Luque, Jean-Gabriel 3 Mitrana, Victor 3 Otto, Friedrich 3 Palioudakis, Alexandros 3 Patrou, Bruno 3 Păun, Gheorghe 3 Ray, Kumar Sankar 3 Rigo, Michel 3 Rozenberg, Grzegorz 3 Seki, Shinnosuke 3 Sinnamon, Corwin W. 3 Staiger, Ludwig 3 Ye, Yuli 3 Zahedi, Mohammad Mehdi 3 Zeugmann, Thomas 2 Abdullah, Rosni 2 Alazemi, Hamed M. K. 2 Arimura, Hiroki 2 Asveld, Peter R. J. 2 Axelsen, Holger Bock 2 Bassino, Frédérique 2 Berglund, Martin 2 Björklund, Henrik 2 Calude, Cristian S. 2 Choffrut, Christian 2 Clerbout, Mireille 2 Ésik, Zoltán 2 Genet, Thomas 2 Ghorani, Maryam ...and 258 more Authors all top 5 Cited in 43 Serials 146 Theoretical Computer Science 68 International Journal of Foundations of Computer Science 30 Information and Computation 18 Journal of Computer and System Sciences 14 Information Processing Letters 9 Theory of Computing Systems 7 Acta Informatica 6 Discrete Applied Mathematics 6 International Journal of Computer Mathematics 6 RAIRO. Informatique Théorique et Applications 6 RAIRO. Theoretical Informatics and Applications 5 Fuzzy Sets and Systems 4 Natural Computing 3 Formal Aspects of Computing 3 Soft Computing 3 RAIRO. Theoretical Informatics and Applications 2 Computational Geometry 2 Journal of Applied Mathematics and Computing 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 Algorithmica 1 Journal of Automated Reasoning 1 International Journal of Approximate Reasoning 1 International Journal of Algebra and Computation 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 Journal of the ACM 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 1 Iranian Journal of Fuzzy Systems 1 Mathematics in Computer Science 1 Algorithms 1 Statistics and Computing 1 Computer Science Review 1 Journal of Mathematics 1 Journal of Logical and Algebraic Methods in Programming all top 5 Cited in 14 Fields 423 Computer science (68-XX) 17 Mathematical logic and foundations (03-XX) 13 Group theory and generalizations (20-XX) 12 Combinatorics (05-XX) 12 Information and communication theory, circuits (94-XX) 3 History and biography (01-XX) 3 Number theory (11-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 3 Numerical analysis (65-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Operations research, mathematical programming (90-XX) 1 Category theory; homological algebra (18-XX) 1 Statistics (62-XX) 1 Biology and other natural sciences (92-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.