Edit Profile (opens in new tab) Yu, Sheng (b. 1950 d. 2012) Co-Author Distance Author ID: yu.sheng Published as: Yu, Sheng; Yu, S. Homepage: https://www.csd.uwo.ca/people/sheng_yu.html External Links: MGP · dblp Documents Indexed: 145 Publications since 1984 6 Contributions as Editor Biographic References: 6 Publications Co-Authors: 63 Co-Authors with 138 Joint Publications 2,249 Co-Co-Authors all top 5 Co-Authors 13 single-authored 57 Salomaa, Kai T. 26 Salomaa, Arto Kustaa 18 Gao, Yuan 10 Câmpeanu, Cezar 10 Culik, Karel II 10 Kari, Lila 10 Santean, Nicolae 9 Ilie, Lucian 9 Wood, Derick 7 Mateescu, Alexandru 6 Păun, Gheorghe 5 Cui, Bo 4 Calude, Cristian S. 4 Jürgensen, Helmut 3 Domaratzki, Michael 3 Jiang, Tao 3 Kinber, Efim B. 3 Konstantinidis, Stavros 3 Lu, Hanlin 3 Păun, Andrei 3 Shallit, Jeffrey Outlaw 3 Thierrin, Gabriel 3 Wong, Prudence Wai-Ha 3 Zhang, Kaizhong 2 Han, Yo-Sub 2 Hurd, Lyman P. 2 Liu, Guangwu 2 Wu, Xiuming 2 Xu, Yinfeng 2 Zan, Jinfeng 1 Calude, Elena 1 Chen, Haiming 1 Dassow, Jürgen 1 Enflo, Per Henrik 1 Ésik, Zoltán 1 Gloor, Greg 1 Granville, Andrew James 1 Holzer, Markus 1 Horváth, Sándor 1 Huerter, Sandra 1 Ibarra, Oscar H. 1 Lakshmanan, V. S. 1 Liu, Ming 1 Martín-Vide, Carlos 1 Masami, Ito 1 Maurer, Hermann A. 1 Moreira, Nelma 1 Navarro, Gonzalo 1 Nicolae, Santean 1 Ojiaku, Jude-Thaddeus 1 Okhotin, Alexander 1 Pachl, Jan K. 1 Qiu, Daowen 1 Reis, Rogério 1 Rozenberg, Grzegorz 1 Seki, Shinnosuke 1 Shan, Baozhen 1 Solis-Oba, Roberto 1 Svozil, Karl 1 Szilard, Andrew L. 1 Zhao, Qing 1 Zheng, Feifeng 1 Zhuang, Qingyu all top 5 Serials 26 Theoretical Computer Science 8 International Journal of Foundations of Computer Science 7 Journal of Automata, Languages and Combinatorics 7 Fundamenta Informaticae 6 Discrete Applied Mathematics 6 International Journal of Computer Mathematics 5 Information and Computation 4 Information Processing Letters 3 Acta Informatica 3 Journal of Computer and System Sciences 3 Bulletin of the European Association for Theoretical Computer Science (EATCS) 3 Journal of Universal Computer Science 3 Lecture Notes in Computer Science 2 Acta Cybernetica 2 Physica D 2 RAIRO. Informatique Théorique et Applications 2 Bulletin of the European Association for Theoretical Computer Science EATCS 1 International Journal of Theoretical Physics 1 Annales Academiae Scientiarum Fennicae. Series A I. Mathematica 1 Publicationes Mathematicae Debrecen 1 SIAM Journal on Computing 1 Annales Societatis Mathematicae Polonae. Series IV 1 International Journal of Parallel Programming 1 Journal of Information Processing and Cybernetics 1 Complex Systems 1 RAIRO. Theoretical Informatics and Applications all top 5 Fields 147 Computer science (68-XX) 6 General and overarching topics; collections (00-XX) 5 Operations research, mathematical programming (90-XX) 3 Mathematical logic and foundations (03-XX) 2 History and biography (01-XX) 2 Quantum theory (81-XX) 1 Group theory and generalizations (20-XX) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 111 Publications have been cited 1,422 times in 796 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 regular languages. Zbl 0978.68087Yu, Sheng 57 2001 Follow automata. Zbl 1059.68063Ilie, Lucian; Yu, Sheng 53 2003 On the limit sets of cellular automata. Zbl 0691.68060Culik, Karel II.; Pachl, Jan; Yu, Sheng 44 1989 Undecidability of CA classification schemes. Zbl 0657.68054Culik, Karel II; Yu, Sheng 42 1988 State complexity of combined operations. Zbl 1124.68056Salomaa, Arto; Salomaa, Kai; Yu, Sheng 39 2007 Subword histories and Parikh matrices. Zbl 1072.68085Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 39 2004 Minimal cover-automata for finite languages. Zbl 0984.68099Câmpeanu, C.; Sântean, N.; Yu, S. 36 2001 Decision problems for patterns. Zbl 0827.68066Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 36 1995 A survey on operational state complexity. Zbl 1380.68253Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng 36 2016 On the state complexity of reversals of regular languages. Zbl 1068.68078Salomaa, Arto; Wood, Derick; Yu, Sheng 35 2004 A formal study of practical regular expressions. Zbl 1101.68443Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 31 2003 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 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060Salomaa, Kai; Yu, Sheng 23 1997 Computation theoretic aspects of cellular automata. Zbl 0729.68052Culik, K. II; Hurd, L. P.; Yu, S. 22 1990 Estimation of state complexity of combined operations. Zbl 1173.68032Ésik, Zoltán; Gao, Yuan; Liu, Guangwu; Yu, Sheng 20 2009 State complexity: recent results and open problems. Zbl 1102.68076Yu, Sheng 19 2005 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093Holzer, Markus; Salomaa, Kai; Yu, Sheng 17 2001 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040Gao, Yuan; Salomaa, Kai; Yu, Sheng 17 2008 Constructions for alternating finite automata. Zbl 0699.68081Fellah, A.; Jürgensen, H.; Yu, S. 17 1990 Characterizing regular languages with polynomial densities. Zbl 1493.68195Szilard, Andrew; Yu, Sheng; Zhang, Kaizhong; Shallit, Jeffrey 17 1992 An efficient algorithm for constructing minimal cover automata for finite languages. Zbl 1066.68062Câmpeanu, Cezar; Păun, Andrei; Yu, Sheng 16 2002 State complexity of basic language operations combined with reversal. Zbl 1154.68073Liu, Guangwu; Martin-Vide, Carlos; Salomaa, Arto; Yu, Sheng 16 2008 Reducing NFAs by invariant equivalences. Zbl 1059.68064Ilie, Lucian; Yu, Sheng 16 2003 Subword occurrences, Parikh matrices and Lyndon images. Zbl 1187.68300Salomaa, Arto; Yu, Sheng 15 2010 Additive distances and quasi-distances between words. Zbl 1258.68074Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 15 2002 On the decomposition of finite languages. Zbl 1013.68099Salomaa, Arto; Yu, Sheng 14 2000 Algorithms for computing small NFAs. Zbl 1014.68082Ilie, Lucian; Yu, Sheng 14 2002 Reducing the size of NFAs by using equivalences and preorders. Zbl 1131.68470Ilie, Lucian; Solis-Oba, Roberto; Yu, Sheng 14 2005 On NFA reductions. Zbl 1055.68545Ilie, Lucian; Navarro, Gonzalo; Yu, Sheng 13 2004 On the existence of prime decompositions. Zbl 1111.68055Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 13 2007 At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. Zbl 0946.68084Kari, Lila; Păun, Gheorghe; Thierrin, Gabriel; Yu, Sheng 12 1999 Hierarchy and equivalence of multi-letter quantum finite automata. Zbl 1179.68073Qiu, Daowen; Yu, Sheng 12 2009 Iterative tree automata. Zbl 0544.68055Culik, Karel II; Yu, Sheng 12 1984 DNA computing, sticker systems, and universality. Zbl 0904.68127Kari, Lila; Păun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto; Yu, Sheng 11 1998 A pumping lemma for deterministic context-free languages. Zbl 0672.68041Yu, Sheng 11 1989 Minimal cover-automata for finite languages. Zbl 0959.68062Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 10 1999 On synchronization in P systems. Zbl 1066.68533Păun, Gheorghe; Yu, Sheng 10 1999 State complexity of two combined operations: catenation-union and catenation-intersection. Zbl 1234.68206Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 10 2011 Mergible states in large NFA. Zbl 1078.68076Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 9 2005 Factorizations of languages and commutativity conditions. Zbl 1065.68063Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 9 2002 On the robustness of primitive words. Zbl 1004.68127Păun, Gheorghe; Santean, Nicolae; Thierrin, Gabriel; Yu, Sheng 9 2002 Subword conditions and subword histories. Zbl 1171.68534Salomaa, Arto; Yu, Sheng 9 2006 On the state complexity of combined operations. Zbl 1160.68431Yu, Sheng 9 2006 Constructing NFAs by optimal use of positions in regular expressions. Zbl 1077.68669Ilie, Lucian; Yu, Sheng 9 2002 Inclusion is undecidable for pattern languages. Zbl 1422.68152Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 9 1993 Pattern expressions and pattern automata. Zbl 1173.68546Câmpeanu, Cezar; Yu, Sheng 8 2004 State complexity of finite and infinite regular languages. Zbl 1024.68543Yu, Sheng 8 2002 Measures of nondeterminism for pushdown automata. Zbl 0822.68070Salomaa, Kai; Yu, Sheng 8 1994 Limited nondeterminism for pushdown automata. Zbl 1023.68621Salomaa, Kai; Yu, Sheng 8 1993 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 State complexity of combined operations with two basic operations. Zbl 1276.68091Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 8 2012 An \(O(n^2)\) algorithm for constructing minimal cover automata for finite languages. Zbl 0989.68070Păun, Andrei; Sântean, Nicolae; Yu, Sheng 7 2001 Physical versus computational complementarity. I. Zbl 0889.68108Calude, Cristian; Calude, Elena; Svozil, Karl; Yu, Sheng 7 1997 Fuzzification of rational and recognizable sets. Zbl 1123.68061Konstantinidis, Stavros; Nicolae, Santean; Yu, Sheng 7 2007 On a public-key cryptosystem based on iterated morphisms and substitutions. Zbl 0636.94007Salomaa, Arto; Yu, Sheng 6 1986 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039Salomaa, Kai; Yu, Sheng 6 1991 Language-theoretic complexity of disjunctive sequences. Zbl 0894.68091Calude, Cristian; Yu, Sheng 6 1997 A property of real-time trellis automata. Zbl 0597.68048Yu, Sheng 5 1986 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 Primality types of instances of the Post correspondence problem. Zbl 0744.68083Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems. Zbl 0743.68085Culik, Karel II.; Yu, Sheng 5 1991 Transducers and the decidability of independence in free monoids. Zbl 0938.68710Jürgensen, H.; Salomaa, K.; Yu, S. 5 1994 State complexity of two combined operations: catenation-star and catenation-reversal. Zbl 1279.68144Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 5 2012 Online scheduling of simple linear deteriorating jobs to minimize the total general completion time. Zbl 1310.68257Yu, Sheng; Wong, Prudence W. H. 5 2013 Iterative tree arrays with logarithmic depth. Zbl 0655.68056Culik, Karel II; Yu, Sheng; Ibarra, Oscar H. 4 1986 Formal languages and global cellular automaton behavior. Zbl 0729.68053Culik, K. II; Hurd, L. P.; Yu, S. 4 1990 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 Minimal covers of formal languages. Zbl 1073.68666Domaratzki, Michael; Shallit, Jeffrey; Yu, Sheng 4 2002 Repetition complexity of words. Zbl 1077.68084Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 4 2002 State complexity of union and intersection of star on \(k\) regular languages. Zbl 1238.68075Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 State complexity of union and intersection of square and reversal on \(k\) regular languages. Zbl 1281.68144Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 Using DNA to solve the bounded Post correspondence problem. Zbl 0951.68039Kari, Lila; Gloor, Greg; Yu, Sheng 3 2000 Pumping and pushdown machines. Zbl 0883.68093Salomaa, Kai; Wood, D.; Yu, Sheng 3 1994 Word complexity and repetitions in words. Zbl 1104.68089Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 3 2004 Degrees of nondeterminism for pushdown automata. Zbl 0925.03175Salomaa, Kai; Yu, Sheng 3 1991 On synchronization languages. Zbl 0843.68055Guo, L.; Salomaa, K.; Yu, S. 3 1996 Derivatives of regular expressions and an application. Zbl 1353.68162Chen, Haiming; Yu, Sheng 3 2012 A note on “An optimal online algorithm for single machine scheduling to minimize total general completion time”. Zbl 1233.68228Yu, Sheng; Wong, Prudence W. H. 3 2012 State complexity research and approximation. Zbl 1221.68151Yu, Sheng; Gao, Yuan 3 2011 State complexity of four combined operations composed of union, intersection, star and reversal. Zbl 1341.68091Gao, Yuan; Yu, Sheng 3 2011 Can the catenation of two weakly sparse languages be dense? Zbl 0644.68102Yu, Sheng 2 1988 Efficient implementation of regular languages using reversed alternating finite automata. Zbl 0951.68061Salomaa, K.; Wu, X.; Yu, S. 2 2000 Cover automata for finite languages. Zbl 1169.68496Yu, Sheng 2 2007 Variants of codes and indecomposable languages. Zbl 1192.68423Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2009 Complexity of E0L structural equivalence. Zbl 0881.68070Salomaa, Kai; Wood, Derick; Yu, Sheng 2 1995 Synchronization expressions with extended join operation. Zbl 0912.68108Salomaa, Kai; Yu, Sheng 2 1998 State complexity of combined operations for prefix-free regular languages. Zbl 1234.68210Han, Yo-Sub; Salomaa, Kai; Yu, Sheng 2 2009 State complexity approximation. Zbl 1456.68085Gao, Yuan; Yu, Sheng 2 2009 Online makespan scheduling of linear deteriorating jobs on parallel machines. Zbl 1354.90056Yu, Sheng; Ojiaku, Jude-Thaddeus; Wong, Prudence W. H.; Xu, Yinfeng 2 2012 State complexity of catenation combined with union and intersection. Zbl 1297.68119Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 2 2011 Nondeterminism degrees for context-free languages. Zbl 1096.68666Salomaa, Kai; Yu, Sheng 2 1996 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 1044.68660Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 1996 State complexity and approximation. Zbl 1255.68094Gao, Yuan; Yu, Sheng 2 2012 A survey on operational state complexity. Zbl 1380.68253Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng 36 2016 Online scheduling of simple linear deteriorating jobs to minimize the total general completion time. Zbl 1310.68257Yu, Sheng; Wong, Prudence W. H. 5 2013 Undecidability of state complexity. Zbl 1401.68167Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 2013 State complexity of combined operations with two basic operations. Zbl 1276.68091Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 8 2012 State complexity of two combined operations: catenation-star and catenation-reversal. Zbl 1279.68144Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 5 2012 State complexity of union and intersection of star on \(k\) regular languages. Zbl 1238.68075Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 State complexity of union and intersection of square and reversal on \(k\) regular languages. Zbl 1281.68144Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 Derivatives of regular expressions and an application. Zbl 1353.68162Chen, Haiming; Yu, Sheng 3 2012 A note on “An optimal online algorithm for single machine scheduling to minimize total general completion time”. Zbl 1233.68228Yu, Sheng; Wong, Prudence W. H. 3 2012 Online makespan scheduling of linear deteriorating jobs on parallel machines. Zbl 1354.90056Yu, Sheng; Ojiaku, Jude-Thaddeus; Wong, Prudence W. H.; Xu, Yinfeng 2 2012 State complexity and approximation. Zbl 1255.68094Gao, Yuan; Yu, Sheng 2 2012 State complexity of two combined operations: catenation-union and catenation-intersection. Zbl 1234.68206Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 10 2011 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 State complexity research and approximation. Zbl 1221.68151Yu, Sheng; Gao, Yuan 3 2011 State complexity of four combined operations composed of union, intersection, star and reversal. Zbl 1341.68091Gao, Yuan; Yu, Sheng 3 2011 State complexity of catenation combined with union and intersection. Zbl 1297.68119Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 2 2011 Subword occurrences, Parikh matrices and Lyndon images. Zbl 1187.68300Salomaa, Arto; Yu, Sheng 15 2010 Estimation of state complexity of combined operations. Zbl 1173.68032Ésik, Zoltán; Gao, Yuan; Liu, Guangwu; Yu, Sheng 20 2009 Hierarchy and equivalence of multi-letter quantum finite automata. Zbl 1179.68073Qiu, Daowen; Yu, Sheng 12 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 approximation. Zbl 1456.68085Gao, Yuan; Yu, Sheng 2 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 basic language operations combined with reversal. Zbl 1154.68073Liu, Guangwu; Martin-Vide, Carlos; Salomaa, Arto; Yu, Sheng 16 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 existence of prime decompositions. Zbl 1111.68055Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 13 2007 Fuzzification of rational and recognizable sets. Zbl 1123.68061Konstantinidis, Stavros; Nicolae, Santean; Yu, Sheng 7 2007 Cover automata for finite languages. Zbl 1169.68496Yu, Sheng 2 2007 Deterministic caterpillar expressions. Zbl 1139.68374Salomaa, Kai; Yu, Sheng; Zan, Jinfeng 1 2007 Subword conditions and subword histories. Zbl 1171.68534Salomaa, Arto; Yu, Sheng 9 2006 On the state complexity of combined operations. Zbl 1160.68431Yu, Sheng 9 2006 State complexity: recent results and open problems. Zbl 1102.68076Yu, Sheng 19 2005 Reducing the size of NFAs by using equivalences and preorders. Zbl 1131.68470Ilie, Lucian; Solis-Oba, Roberto; Yu, Sheng 14 2005 Mergible states in large NFA. Zbl 1078.68076Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 9 2005 Subword histories and Parikh matrices. Zbl 1072.68085Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 39 2004 On the state complexity of reversals of regular languages. Zbl 1068.68078Salomaa, Arto; Wood, Derick; Yu, Sheng 35 2004 On NFA reductions. Zbl 1055.68545Ilie, Lucian; Navarro, Gonzalo; Yu, Sheng 13 2004 Pattern expressions and pattern automata. Zbl 1173.68546Câmpeanu, Cezar; Yu, Sheng 8 2004 Word complexity and repetitions in words. Zbl 1104.68089Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 3 2004 Follow automata. Zbl 1059.68063Ilie, Lucian; Yu, Sheng 53 2003 A formal study of practical regular expressions. Zbl 1101.68443Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 31 2003 Reducing NFAs by invariant equivalences. Zbl 1059.68064Ilie, Lucian; Yu, Sheng 16 2003 Regex and extended regex. Zbl 1033.68056Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 1 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 30 2002 An efficient algorithm for constructing minimal cover automata for finite languages. Zbl 1066.68062Câmpeanu, Cezar; Păun, Andrei; Yu, Sheng 16 2002 Additive distances and quasi-distances between words. Zbl 1258.68074Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 15 2002 Algorithms for computing small NFAs. Zbl 1014.68082Ilie, Lucian; Yu, Sheng 14 2002 Factorizations of languages and commutativity conditions. Zbl 1065.68063Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 9 2002 On the robustness of primitive words. Zbl 1004.68127Păun, Gheorghe; Santean, Nicolae; Thierrin, Gabriel; Yu, Sheng 9 2002 Constructing NFAs by optimal use of positions in regular expressions. Zbl 1077.68669Ilie, Lucian; Yu, Sheng 9 2002 State complexity of finite and infinite regular languages. Zbl 1024.68543Yu, Sheng 8 2002 Minimal covers of formal languages. Zbl 1073.68666Domaratzki, Michael; Shallit, Jeffrey; Yu, Sheng 4 2002 Repetition complexity of words. Zbl 1077.68084Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 4 2002 A sharpening of the Parikh mapping. Zbl 1005.68092Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 66 2001 State complexity of regular languages. Zbl 0978.68087Yu, Sheng 57 2001 Minimal cover-automata for finite languages. Zbl 0984.68099Câmpeanu, C.; Sântean, N.; Yu, S. 36 2001 State complexity of basic operations on finite languages. Zbl 1050.68091Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 31 2001 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093Holzer, Markus; Salomaa, Kai; Yu, Sheng 17 2001 An \(O(n^2)\) algorithm for constructing minimal cover automata for finite languages. Zbl 0989.68070Păun, Andrei; Sântean, Nicolae; Yu, Sheng 7 2001 Metric lexical analysis. Zbl 1050.68090Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 1 2001 On the decomposition of finite languages. Zbl 1013.68099Salomaa, Arto; Yu, Sheng 14 2000 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 Using DNA to solve the bounded Post correspondence problem. Zbl 0951.68039Kari, Lila; Gloor, Greg; Yu, Sheng 3 2000 Efficient implementation of regular languages using reversed alternating finite automata. Zbl 0951.68061Salomaa, K.; Wu, X.; Yu, S. 2 2000 At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. Zbl 0946.68084Kari, Lila; Păun, Gheorghe; Thierrin, Gabriel; Yu, Sheng 12 1999 Minimal cover-automata for finite languages. Zbl 0959.68062Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 10 1999 On synchronization in P systems. Zbl 1066.68533Păun, Gheorghe; Yu, Sheng 10 1999 DNA computing, sticker systems, and universality. Zbl 0904.68127Kari, Lila; Păun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto; Yu, Sheng 11 1998 Synchronization expressions with extended join operation. Zbl 0912.68108Salomaa, Kai; Yu, Sheng 2 1998 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060Salomaa, Kai; Yu, Sheng 23 1997 Physical versus computational complementarity. I. Zbl 0889.68108Calude, Cristian; Calude, Elena; Svozil, Karl; Yu, Sheng 7 1997 Language-theoretic complexity of disjunctive sequences. Zbl 0894.68091Calude, Cristian; Yu, Sheng 6 1997 Rewriting rules for synchronization languages. Zbl 0884.68072Salomaa, Kai; Yu, Sheng 1 1997 On synchronization languages. Zbl 0843.68055Guo, L.; Salomaa, K.; Yu, S. 3 1996 Nondeterminism degrees for context-free languages. Zbl 1096.68666Salomaa, Kai; Yu, Sheng 2 1996 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 1044.68660Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 1996 Structural equivalence and ET0L grammars. Zbl 0871.68119Salomaa, Kai; Wood, Derick; Yu, Sheng 1 1996 Decision problems for patterns. Zbl 0827.68066Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 36 1995 Complexity of E0L structural equivalence. Zbl 0881.68070Salomaa, Kai; Wood, Derick; Yu, Sheng 2 1995 P, NP, and the Post correspondence problem. Zbl 0834.68033Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 1995 The state complexities of some basic operations on regular languages. Zbl 0795.68112Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai 140 1994 Pattern languages with and without erasing. Zbl 0939.68690Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 27 1994 Measures of nondeterminism for pushdown automata. Zbl 0822.68070Salomaa, Kai; Yu, Sheng 8 1994 Transducers and the decidability of independence in free monoids. Zbl 0938.68710Jürgensen, H.; Salomaa, K.; Yu, S. 5 1994 Pumping and pushdown machines. Zbl 0883.68093Salomaa, Kai; Wood, D.; Yu, Sheng 3 1994 On sparse languages \(L\) such that \(LL= \Sigma^*\). Zbl 0813.68124Enflo, Per; Granville, Andrew; Shallit, Jeffrey; Yu, Sheng 1 1994 Inclusion is undecidable for pattern languages. Zbl 1422.68152Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 9 1993 Limited nondeterminism for pushdown automata. Zbl 1023.68621Salomaa, Kai; Yu, Sheng 8 1993 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 Characterizing regular languages with polynomial densities. Zbl 1493.68195Szilard, Andrew; Yu, Sheng; Zhang, Kaizhong; Shallit, Jeffrey 17 1992 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039Salomaa, Kai; Yu, Sheng 6 1991 Primality types of instances of the Post correspondence problem. Zbl 0744.68083Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems. Zbl 0743.68085Culik, Karel II.; Yu, Sheng 5 1991 Degrees of nondeterminism for pushdown automata. Zbl 0925.03175Salomaa, Kai; Yu, Sheng 3 1991 Computation theoretic aspects of cellular automata. Zbl 0729.68052Culik, K. II; Hurd, L. P.; Yu, S. 22 1990 ...and 11 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 768 Authors 70 Salomaa, Kai T. 51 Yu, Sheng 35 Kutrib, Martin 31 Holzer, Markus 31 Salomaa, Arto Kustaa 29 Jirásková, Galina 27 Han, Yo-Sub 21 Reidenbach, Daniel 20 Brzozowski, Janusz Antoni 19 Okhotin, Alexander 18 Teh, Wen Chean 17 Kari, Lila 15 Ko, Sang-Ki 15 Subramanian, Kumbakonam Govindarajan 14 Moreira, Nelma 14 Ng, Timothy 13 Reis, Rogério 12 Caron, Pascal 12 Champarnaud, Jean-Marc 11 Freydenberger, Dominik D. 11 Gruber, Hermann 11 Qiu, Daowen 11 Schmid, Markus L. 11 Shallit, Jeffrey Outlaw 10 Atanasiu, Adrian 10 Gao, Yuan 10 Malcher, Andreas 10 Pighizzini, Giovanni 9 Fernau, Henning 9 Ipate, Florentin 9 Margara, Luciano 9 Szykuła, Marek 9 Wendlandt, Matthias 8 Bera, Somnath 8 Ćirić, Miroslav D. 8 Culik, Karel II 8 Domaratzki, Michael 8 Formenti, Enrico 8 Gruska, Jozef 8 Hospodár, Michal 8 Kari, Jarkko 8 Li, Lvzhou 8 Luque, Jean-Gabriel 8 Mahalingam, Kalpana 8 Mateescu, Alexandru 8 Mignot, Ludovic 8 Rappaport, David 8 Šebej, Juraj 8 Wood, Derick 8 Zheng, Shenggen 7 Broda, Sabine 7 Cattaneo, Gianpiero 7 Dassow, Jürgen 7 Geffert, Viliam 7 Gheorghe, Marian 7 Karhumaki, Juhani 7 Manea, Florin 7 Poovanandran, Ghajendran 6 Calude, Cristian S. 6 Câmpeanu, Cezar 6 Ibarra, Oscar H. 6 Ignjatović, Jelena 6 Ilie, Lucian 6 Machiavelo, António 6 Mathew, Lisa 6 Mitrana, Victor 6 Nagar, Atulya K. 6 Piao, Xiaoxue 5 Černý, Anton 5 Cho, Da-Jung 5 Day, Joel D. 5 Hoffmann, Stefan 5 Jakobi, Sebastian 5 Lange, Steffen 5 Manzini, Giovanni 5 Mereghetti, Carlo 5 Palano, Beatrice 5 Palioudakis, Alexandros 5 Patrou, Bruno 5 Păun, Gheorghe 5 Schneider, Johannes C. 5 Ziadi, Djelloul 4 Bednárová, Zuzana 4 Court, Edwin Hamel-De Le 4 Cui, Bo 4 Dennunzio, Alberto 4 Durand, Bruno 4 Eom, Hae-Sung 4 Fazekas, Szilárd Zsolt 4 Flocchini, Paola 4 Garcia, Pedro 4 Guingne, Franck 4 Hunt, Harry Bowen III 4 Konur, Savas 4 Kůrka, Petr 4 Lipponen, Marjo 4 López , Damián 4 Maletti, Andreas 4 Mateus, Paulo C. 4 Mercaş, Robert George ...and 668 more Authors all top 5 Cited in 83 Serials 225 Theoretical Computer Science 92 International Journal of Foundations of Computer Science 42 Information and Computation 29 Journal of Computer and System Sciences 20 Discrete Applied Mathematics 18 Acta Informatica 18 Information Processing Letters 18 Physica D 11 RAIRO. Theoretical Informatics and Applications 9 International Journal of Computer Mathematics 9 Theory of Computing Systems 8 Fuzzy Sets and Systems 8 Information Sciences 7 RAIRO. Theoretical Informatics and Applications 7 Natural Computing 5 RAIRO. Informatique Théorique et Applications 4 Journal of Automata, Languages and Combinatorics 4 Soft Computing 3 International Journal of Theoretical Physics 3 Chaos, Solitons and Fractals 3 Algorithmica 3 International Journal of Algebra and Computation 3 MSCS. Mathematical Structures in Computer Science 3 Chaos 2 International Journal of General Systems 2 Journal of Algebra 2 Mathematica Slovaca 2 Semigroup Forum 2 Journal of Systems Science and Complexity 2 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 2 Journal of Mathematics 2 Journal of Logical and Algebraic Methods in Programming 2 Journal of Membrane Computing 1 Advances in Applied Probability 1 Computer Physics Communications 1 Discrete Mathematics 1 Acta Mathematica Vietnamica 1 Algebra and Logic 1 Applied Mathematics and Computation 1 Canadian Journal of Mathematics 1 Inventiones Mathematicae 1 Journal of Pure and Applied Algebra 1 Journal of Soviet Mathematics 1 Mathematics and Computers in Simulation 1 Mathematische Zeitschrift 1 Proceedings of the American Mathematical Society 1 Advances in Applied Mathematics 1 Ergodic Theory and Dynamical Systems 1 Annals of Pure and Applied Logic 1 Bulletin of the Iranian Mathematical Society 1 Acta Mathematicae Applicatae Sinica. English Series 1 New Generation Computing 1 Forum Mathematicum 1 Formal Aspects of Computing 1 Annals of Operations Research 1 Designs, Codes and Cryptography 1 Indagationes Mathematicae. New Series 1 Foundations of Computing and Decision Sciences 1 The Australasian Journal of Combinatorics 1 Russian Mathematics 1 Journal of Logic, Language and Information 1 Applied Mathematics. Series B (English Edition) 1 Filomat 1 The Bulletin of Symbolic Logic 1 Complexity 1 Nonlinear Dynamics 1 Journal of Combinatorial Optimization 1 Journal of Scheduling 1 Journal of the ACM 1 Annals of Combinatorics 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Fundamenta Informaticae 1 JMMA. Journal of Mathematical Modelling and Algorithms 1 Quantum Information Processing 1 Journal of Intelligent and Fuzzy Systems 1 4OR 1 Journal of Discrete Algorithms 1 Mathematics in Computer Science 1 Logical Methods in Computer Science 1 Ars Mathematica Contemporanea 1 Frontiers of Computer Science in China 1 Computer Science Review 1 Advances in Combinatorics all top 5 Cited in 25 Fields 759 Computer science (68-XX) 45 Dynamical systems and ergodic theory (37-XX) 33 Mathematical logic and foundations (03-XX) 33 Combinatorics (05-XX) 26 Group theory and generalizations (20-XX) 20 Information and communication theory, circuits (94-XX) 12 Number theory (11-XX) 11 Quantum theory (81-XX) 10 Biology and other natural sciences (92-XX) 9 Operations research, mathematical programming (90-XX) 5 Linear and multilinear algebra; matrix theory (15-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Statistical mechanics, structure of matter (82-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 General and overarching topics; collections (00-XX) 2 History and biography (01-XX) 2 Associative rings and algebras (16-XX) 2 Probability theory and stochastic processes (60-XX) 2 Systems theory; control (93-XX) 1 Field theory and polynomials (12-XX) 1 Commutative algebra (13-XX) 1 Convex and discrete geometry (52-XX) 1 General topology (54-XX) 1 Manifolds and cell complexes (57-XX) 1 Numerical analysis (65-XX) Citations by Year