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: http://recursed.blogspot.com/2012/01/in-memory-of-sheng-yu.html External Links: MGP · Wikidata · dblp Documents Indexed: 149 Publications since 1984, including 2 Additional arXiv Preprints 6 Contributions as Editor Biographic References: 6 Publications Co-Authors: 64 Co-Authors with 140 Joint Publications 2,326 Co-Co-Authors all top 5 Co-Authors 13 single-authored 58 Salomaa, Kai T. 26 Salomaa, Arto Kustaa 18 Gao, Yuan 10 Câmpeanu, Cezar 10 Culik, Karel II 10 Kari, Lila 10 Santean, Nicolae 10 Wood, Derick 9 Ilie, Lucian 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 Campos-Náñez, Enrique 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 Xu, Haitong 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 149 Computer science (68-XX) 6 General and overarching topics; collections (00-XX) 6 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 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 112 Publications have been cited 1,483 times in 844 Documents Cited by ▼ Year ▼ The state complexities of some basic operations on regular languages. Zbl 0795.68112 Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai 147 1994 A sharpening of the Parikh mapping. Zbl 1005.68092 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 72 2001 State complexity of regular languages. Zbl 0978.68087 Yu, Sheng 57 2001 Follow automata. Zbl 1059.68063 Ilie, Lucian; Yu, Sheng 55 2003 On the limit sets of cellular automata. Zbl 0691.68060 Culik, Karel II.; Pachl, Jan; Yu, Sheng 47 1989 Subword histories and Parikh matrices. Zbl 1072.68085 Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 44 2004 Undecidability of CA classification schemes. Zbl 0657.68054 Culik, Karel II; Yu, Sheng 43 1988 A survey on operational state complexity. Zbl 1380.68253 Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng 42 2016 State complexity of combined operations. Zbl 1124.68056 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 40 2007 Minimal cover-automata for finite languages. Zbl 0984.68099 Câmpeanu, C.; Sântean, N.; Yu, S. 36 2001 Decision problems for patterns. Zbl 0827.68066 Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 36 1995 On the state complexity of reversals of regular languages. Zbl 1068.68078 Salomaa, Arto; Wood, Derick; Yu, Sheng 36 2004 State complexity of basic operations on finite languages. Zbl 1050.68091 Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 33 2001 A formal study of practical regular expressions. Zbl 1101.68443 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 32 2003 Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 30 2002 Pattern languages with and without erasing. Zbl 0939.68690 Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 27 1994 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060 Salomaa, Kai; Yu, Sheng 23 1997 Computation theoretic aspects of cellular automata. Zbl 0729.68052 Culik, K. II; Hurd, L. P.; Yu, S. 23 1990 Characterizing regular languages with polynomial densities. Zbl 1493.68195 Szilard, Andrew; Yu, Sheng; Zhang, Kaizhong; Shallit, Jeffrey 22 1992 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.68076 Yu, Sheng 19 2005 State complexity of basic language operations combined with reversal. Zbl 1154.68073 Liu, Guangwu; Martin-Vide, Carlos; Salomaa, Arto; Yu, Sheng 17 2008 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093 Holzer, Markus; Salomaa, Kai; Yu, Sheng 17 2001 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040 Gao, Yuan; Salomaa, Kai; Yu, Sheng 17 2008 Constructions for alternating finite automata. Zbl 0699.68081 Fellah, A.; Jürgensen, H.; Yu, S. 17 1990 Additive distances and quasi-distances between words. Zbl 1258.68074 Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 16 2002 An efficient algorithm for constructing minimal cover automata for finite languages. Zbl 1066.68062 Câmpeanu, Cezar; Păun, Andrei; Yu, Sheng 16 2002 Reducing NFAs by invariant equivalences. Zbl 1059.68064 Ilie, Lucian; Yu, Sheng 16 2003 On the decomposition of finite languages. Zbl 1013.68099 Salomaa, Arto; Yu, Sheng 15 2000 Subword occurrences, Parikh matrices and Lyndon images. Zbl 1187.68300 Salomaa, Arto; Yu, Sheng 15 2010 Algorithms for computing small NFAs. Zbl 1014.68082 Ilie, Lucian; Yu, Sheng 14 2002 Reducing the size of NFAs by using equivalences and preorders. Zbl 1131.68470 Ilie, Lucian; Solis-Oba, Roberto; Yu, Sheng 14 2005 At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. Zbl 0946.68084 Kari, Lila; Păun, Gheorghe; Thierrin, Gabriel; Yu, Sheng 13 1999 Hierarchy and equivalence of multi-letter quantum finite automata. Zbl 1179.68073 Qiu, Daowen; Yu, Sheng 13 2009 On the existence of prime decompositions. Zbl 1111.68055 Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 13 2007 On NFA reductions. Zbl 1055.68545 Ilie, Lucian; Navarro, Gonzalo; Yu, Sheng 13 2004 Iterative tree automata. Zbl 0544.68055 Culik, Karel II; Yu, Sheng 13 1984 DNA computing, sticker systems, and universality. Zbl 0904.68127 Kari, Lila; Păun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto; Yu, Sheng 12 1998 A pumping lemma for deterministic context-free languages. Zbl 0672.68041 Yu, Sheng 12 1989 On synchronization in P systems. Zbl 1066.68533 Păun, Gheorghe; Yu, Sheng 11 1999 Minimal cover-automata for finite languages. Zbl 0959.68062 Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 10 1999 Inclusion is undecidable for pattern languages. Zbl 1422.68152 Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 10 1993 State complexity of two combined operations: catenation-union and catenation-intersection. Zbl 1234.68206 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 10 2011 Subword conditions and subword histories. Zbl 1171.68534 Salomaa, Arto; Yu, Sheng 9 2006 Transition complexity of incomplete DFAs. Zbl 1230.68130 Gao, Yuan; Salomaa, Kai; Yu, Sheng 9 2011 On the robustness of primitive words. Zbl 1004.68127 Păun, Gheorghe; Santean, Nicolae; Thierrin, Gabriel; Yu, Sheng 9 2002 On the state complexity of combined operations. Zbl 1160.68431 Yu, Sheng 9 2006 Limited nondeterminism for pushdown automata. Zbl 1023.68621 Salomaa, Kai; Yu, Sheng 9 1993 Factorizations of languages and commutativity conditions. Zbl 1065.68063 Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 9 2002 Mergible states in large NFA. Zbl 1078.68076 Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 9 2005 Constructing NFAs by optimal use of positions in regular expressions. Zbl 1077.68669 Ilie, Lucian; Yu, Sheng 9 2002 Measures of nondeterminism for pushdown automata. Zbl 0822.68070 Salomaa, Kai; Yu, Sheng 8 1994 State complexity of finite and infinite regular languages. Zbl 1024.68543 Yu, Sheng 8 2002 Pattern expressions and pattern automata. Zbl 1173.68546 Câmpeanu, Cezar; Yu, Sheng 8 2004 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 State complexity of combined operations with two basic operations. Zbl 1276.68091 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 8 2012 Physical versus computational complementarity. I. Zbl 0889.68108 Calude, Cristian; Calude, Elena; Svozil, Karl; Yu, Sheng 7 1997 An \(O(n^2)\) algorithm for constructing minimal cover automata for finite languages. Zbl 0989.68070 Păun, Andrei; Sântean, Nicolae; Yu, Sheng 7 2001 Fuzzification of rational and recognizable sets. Zbl 1123.68061 Konstantinidis, Stavros; Nicolae, Santean; Yu, Sheng 7 2007 On a public-key cryptosystem based on iterated morphisms and substitutions. Zbl 0636.94007 Salomaa, Arto; Yu, Sheng 7 1986 Transducers and the decidability of independence in free monoids. Zbl 0938.68710 Jürgensen, H.; Salomaa, K.; Yu, S. 6 1994 Language-theoretic complexity of disjunctive sequences. Zbl 0894.68091 Calude, Cristian; Yu, Sheng 6 1997 A property of real-time trellis automata. Zbl 0597.68048 Yu, Sheng 6 1986 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039 Salomaa, Kai; Yu, Sheng 6 1991 Pumping and pushdown machines. Zbl 0883.68093 Salomaa, Kai; Wood, D.; Yu, Sheng 5 1994 Iterative tree arrays with logarithmic depth. Zbl 0655.68056 Culik, Karel II; Yu, Sheng; Ibarra, Oscar H. 5 1986 Alternating finite automata and star-free languages. Zbl 0944.68090 Salomaa, K.; Yu, S. 5 2000 On fairness of many-dimensional trajectories. Zbl 0959.68068 Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 5 2000 Primality types of instances of the Post correspondence problem. Zbl 0744.68083 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems. Zbl 0743.68085 Culik, Karel II.; Yu, Sheng 5 1991 State complexity of two combined operations: catenation-star and catenation-reversal. Zbl 1279.68144 Cui, 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.68257 Yu, Sheng; Wong, Prudence W. H. 5 2013 State complexity of union and intersection of star on \(k\) regular languages. Zbl 1238.68075 Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 Structural equivalence and ET0L grammars. Zbl 0794.68093 Salomaa, Kai; Wood, Derick; Yu, Sheng 4 1993 Decidability of the intercode property. Zbl 0824.68061 Jürgensen, H.; Salomaa, K.; Yu, S. 4 1993 Minimal covers of formal languages. Zbl 1073.68666 Domaratzki, Michael; Shallit, Jeffrey; Yu, Sheng 4 2002 Repetition complexity of words. Zbl 1077.68084 Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 4 2002 Formal languages and global cellular automaton behavior. Zbl 0729.68053 Culik, K. II; Hurd, L. P.; Yu, S. 4 1990 State complexity of union and intersection of square and reversal on \(k\) regular languages. Zbl 1281.68144 Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 Derivatives of regular expressions and an application. Zbl 1353.68162 Chen, Haiming; Yu, Sheng 3 2012 Degrees of nondeterminism for pushdown automata. Zbl 0925.03175 Salomaa, Kai; Yu, Sheng 3 1991 Using DNA to solve the bounded Post correspondence problem. Zbl 0951.68039 Kari, Lila; Gloor, Greg; Yu, Sheng 3 2000 Word complexity and repetitions in words. Zbl 1104.68089 Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 3 2004 On synchronization languages. Zbl 0843.68055 Guo, L.; Salomaa, K.; Yu, S. 3 1996 A note on “An optimal online algorithm for single machine scheduling to minimize total general completion time”. Zbl 1233.68228 Yu, Sheng; Wong, Prudence W. H. 3 2012 State complexity research and approximation. Zbl 1221.68151 Yu, Sheng; Gao, Yuan 3 2011 State complexity of four combined operations composed of union, intersection, star and reversal. Zbl 1341.68091 Gao, Yuan; Yu, Sheng 3 2011 Nondeterminism degrees for context-free languages. Zbl 1096.68666 Salomaa, Kai; Yu, Sheng 2 1996 Synchronization expressions with extended join operation. Zbl 0912.68108 Salomaa, Kai; Yu, Sheng 2 1998 Complexity of E0L structural equivalence. Zbl 0881.68070 Salomaa, Kai; Wood, Derick; Yu, Sheng 2 1995 Can the catenation of two weakly sparse languages be dense? Zbl 0644.68102 Yu, Sheng 2 1988 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 1044.68660 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 1996 Efficient implementation of regular languages using reversed alternating finite automata. Zbl 0951.68061 Salomaa, K.; Wu, X.; Yu, S. 2 2000 State complexity of combined operations for prefix-free regular languages. Zbl 1234.68210 Han, Yo-Sub; Salomaa, Kai; Yu, Sheng 2 2009 State complexity approximation. Zbl 1456.68085 Gao, Yuan; Yu, Sheng 2 2009 Cover automata for finite languages. Zbl 1169.68496 Yu, Sheng 2 2007 State complexity of catenation combined with union and intersection. Zbl 1297.68119 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 2 2011 State complexity and approximation. Zbl 1255.68094 Gao, Yuan; Yu, Sheng 2 2012 Online makespan scheduling of linear deteriorating jobs on parallel machines. Zbl 1354.90056 Yu, Sheng; Ojiaku, Jude-Thaddeus; Wong, Prudence W. H.; Xu, Yinfeng 2 2012 Developments in language theory. 14th international conference, DLT 2010, London, ON, Canada, August 17–20, 2010. Proceedings. Zbl 1194.68035 2 2010 A survey on operational state complexity. Zbl 1380.68253 Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng 42 2016 Online scheduling of simple linear deteriorating jobs to minimize the total general completion time. Zbl 1310.68257 Yu, Sheng; Wong, Prudence W. H. 5 2013 Undecidability of state complexity. Zbl 1401.68167 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 2013 State complexity of combined operations with two basic operations. Zbl 1276.68091 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 8 2012 State complexity of two combined operations: catenation-star and catenation-reversal. Zbl 1279.68144 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 5 2012 State complexity of union and intersection of star on \(k\) regular languages. Zbl 1238.68075 Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 State complexity of union and intersection of square and reversal on \(k\) regular languages. Zbl 1281.68144 Gao, Yuan; Kari, Lila; Yu, Sheng 4 2012 Derivatives of regular expressions and an application. Zbl 1353.68162 Chen, Haiming; Yu, Sheng 3 2012 A note on “An optimal online algorithm for single machine scheduling to minimize total general completion time”. Zbl 1233.68228 Yu, Sheng; Wong, Prudence W. H. 3 2012 State complexity and approximation. Zbl 1255.68094 Gao, Yuan; Yu, Sheng 2 2012 Online makespan scheduling of linear deteriorating jobs on parallel machines. Zbl 1354.90056 Yu, Sheng; Ojiaku, Jude-Thaddeus; Wong, Prudence W. H.; Xu, Yinfeng 2 2012 State complexity of two combined operations: catenation-union and catenation-intersection. Zbl 1234.68206 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 10 2011 Transition complexity of incomplete DFAs. Zbl 1230.68130 Gao, Yuan; Salomaa, Kai; Yu, Sheng 9 2011 Undecidability of the state complexity of composed regular operations. Zbl 1330.68179 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 8 2011 State complexity research and approximation. Zbl 1221.68151 Yu, Sheng; Gao, Yuan 3 2011 State complexity of four combined operations composed of union, intersection, star and reversal. Zbl 1341.68091 Gao, Yuan; Yu, Sheng 3 2011 State complexity of catenation combined with union and intersection. Zbl 1297.68119 Cui, Bo; Gao, Yuan; Kari, Lila; Yu, Sheng 2 2011 Subword occurrences, Parikh matrices and Lyndon images. Zbl 1187.68300 Salomaa, Arto; Yu, Sheng 15 2010 Developments in language theory. 14th international conference, DLT 2010, London, ON, Canada, August 17–20, 2010. Proceedings. Zbl 1194.68035 2 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.68073 Qiu, Daowen; Yu, Sheng 13 2009 State complexity of combined operations for prefix-free regular languages. Zbl 1234.68210 Han, Yo-Sub; Salomaa, Kai; Yu, Sheng 2 2009 State complexity approximation. Zbl 1456.68085 Gao, Yuan; Yu, Sheng 2 2009 Variants of codes and indecomposable languages. Zbl 1192.68423 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 2009 State complexity of basic language operations combined with reversal. Zbl 1154.68073 Liu, Guangwu; Martin-Vide, Carlos; Salomaa, Arto; Yu, Sheng 17 2008 The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040 Gao, Yuan; Salomaa, Kai; Yu, Sheng 17 2008 Length codes, products of languages and primality. Zbl 1156.68464 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 2008 State complexity of combined operations. Zbl 1124.68056 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 40 2007 On the existence of prime decompositions. Zbl 1111.68055 Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng 13 2007 Fuzzification of rational and recognizable sets. Zbl 1123.68061 Konstantinidis, Stavros; Nicolae, Santean; Yu, Sheng 7 2007 Cover automata for finite languages. Zbl 1169.68496 Yu, Sheng 2 2007 Deterministic caterpillar expressions. Zbl 1139.68374 Salomaa, Kai; Yu, Sheng; Zan, Jinfeng 1 2007 Subword conditions and subword histories. Zbl 1171.68534 Salomaa, Arto; Yu, Sheng 9 2006 On the state complexity of combined operations. Zbl 1160.68431 Yu, Sheng 9 2006 State complexity: recent results and open problems. Zbl 1102.68076 Yu, Sheng 19 2005 Reducing the size of NFAs by using equivalences and preorders. Zbl 1131.68470 Ilie, Lucian; Solis-Oba, Roberto; Yu, Sheng 14 2005 Mergible states in large NFA. Zbl 1078.68076 Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 9 2005 Subword histories and Parikh matrices. Zbl 1072.68085 Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 44 2004 On the state complexity of reversals of regular languages. Zbl 1068.68078 Salomaa, Arto; Wood, Derick; Yu, Sheng 36 2004 On NFA reductions. Zbl 1055.68545 Ilie, Lucian; Navarro, Gonzalo; Yu, Sheng 13 2004 Pattern expressions and pattern automata. Zbl 1173.68546 Câmpeanu, Cezar; Yu, Sheng 8 2004 Word complexity and repetitions in words. Zbl 1104.68089 Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 3 2004 Follow automata. Zbl 1059.68063 Ilie, Lucian; Yu, Sheng 55 2003 A formal study of practical regular expressions. Zbl 1101.68443 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 32 2003 Reducing NFAs by invariant equivalences. Zbl 1059.68064 Ilie, Lucian; Yu, Sheng 16 2003 Deletion on trajectories and commutative closure. Zbl 1040.68053 Domaratzki, Michael; Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 1 2003 Regex and extended regex. Zbl 1033.68056 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 1 2003 Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057 Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng 30 2002 Additive distances and quasi-distances between words. Zbl 1258.68074 Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 16 2002 An efficient algorithm for constructing minimal cover automata for finite languages. Zbl 1066.68062 Câmpeanu, Cezar; Păun, Andrei; Yu, Sheng 16 2002 Algorithms for computing small NFAs. Zbl 1014.68082 Ilie, Lucian; Yu, Sheng 14 2002 On the robustness of primitive words. Zbl 1004.68127 Păun, Gheorghe; Santean, Nicolae; Thierrin, Gabriel; Yu, Sheng 9 2002 Factorizations of languages and commutativity conditions. Zbl 1065.68063 Mateescu, Alexandru; Salomaa, Arto; Yu, Sheng 9 2002 Constructing NFAs by optimal use of positions in regular expressions. Zbl 1077.68669 Ilie, Lucian; Yu, Sheng 9 2002 State complexity of finite and infinite regular languages. Zbl 1024.68543 Yu, Sheng 8 2002 Minimal covers of formal languages. Zbl 1073.68666 Domaratzki, Michael; Shallit, Jeffrey; Yu, Sheng 4 2002 Repetition complexity of words. Zbl 1077.68084 Ilie, Lucian; Yu, Sheng; Zhang, Kaizhong 4 2002 A sharpening of the Parikh mapping. Zbl 1005.68092 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 72 2001 State complexity of regular languages. Zbl 0978.68087 Yu, Sheng 57 2001 Minimal cover-automata for finite languages. Zbl 0984.68099 Câmpeanu, C.; Sântean, N.; Yu, S. 36 2001 State complexity of basic operations on finite languages. Zbl 1050.68091 Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng 33 2001 On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093 Holzer, Markus; Salomaa, Kai; Yu, Sheng 17 2001 An \(O(n^2)\) algorithm for constructing minimal cover automata for finite languages. Zbl 0989.68070 Păun, Andrei; Sântean, Nicolae; Yu, Sheng 7 2001 Metric lexical analysis. Zbl 1050.68090 Calude, Cristian S.; Salomaa, Kai; Yu, Sheng 1 2001 On the decomposition of finite languages. Zbl 1013.68099 Salomaa, Arto; Yu, Sheng 15 2000 Alternating finite automata and star-free languages. Zbl 0944.68090 Salomaa, K.; Yu, S. 5 2000 On fairness of many-dimensional trajectories. Zbl 0959.68068 Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng 5 2000 Using DNA to solve the bounded Post correspondence problem. Zbl 0951.68039 Kari, Lila; Gloor, Greg; Yu, Sheng 3 2000 Efficient implementation of regular languages using reversed alternating finite automata. Zbl 0951.68061 Salomaa, 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.68084 Kari, Lila; Păun, Gheorghe; Thierrin, Gabriel; Yu, Sheng 13 1999 On synchronization in P systems. Zbl 1066.68533 Păun, Gheorghe; Yu, Sheng 11 1999 Minimal cover-automata for finite languages. Zbl 0959.68062 Câmpeanu, Cezar; Sântean, Nicolae; Yu, Sheng 10 1999 DNA computing, sticker systems, and universality. Zbl 0904.68127 Kari, Lila; Păun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto; Yu, Sheng 12 1998 Synchronization expressions with extended join operation. Zbl 0912.68108 Salomaa, Kai; Yu, Sheng 2 1998 NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060 Salomaa, Kai; Yu, Sheng 23 1997 Physical versus computational complementarity. I. Zbl 0889.68108 Calude, Cristian; Calude, Elena; Svozil, Karl; Yu, Sheng 7 1997 Language-theoretic complexity of disjunctive sequences. Zbl 0894.68091 Calude, Cristian; Yu, Sheng 6 1997 Rewriting rules for synchronization languages. Zbl 0884.68072 Salomaa, Kai; Yu, Sheng 1 1997 On synchronization languages. Zbl 0843.68055 Guo, L.; Salomaa, K.; Yu, S. 3 1996 Nondeterminism degrees for context-free languages. Zbl 1096.68666 Salomaa, Kai; Yu, Sheng 2 1996 Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 1044.68660 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 2 1996 Structural equivalence and ET0L grammars. Zbl 0871.68119 Salomaa, Kai; Wood, Derick; Yu, Sheng 1 1996 Decision problems for patterns. Zbl 0827.68066 Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 36 1995 Complexity of E0L structural equivalence. Zbl 0881.68070 Salomaa, Kai; Wood, Derick; Yu, Sheng 2 1995 P, NP, and the Post correspondence problem. Zbl 0834.68033 Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 1 1995 The state complexities of some basic operations on regular languages. Zbl 0795.68112 Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai 147 1994 Pattern languages with and without erasing. Zbl 0939.68690 Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 27 1994 Measures of nondeterminism for pushdown automata. Zbl 0822.68070 Salomaa, Kai; Yu, Sheng 8 1994 Transducers and the decidability of independence in free monoids. Zbl 0938.68710 Jürgensen, H.; Salomaa, K.; Yu, S. 6 1994 Pumping and pushdown machines. Zbl 0883.68093 Salomaa, Kai; Wood, D.; Yu, Sheng 5 1994 On sparse languages \(L\) such that \(LL= \Sigma^*\). Zbl 0813.68124 Enflo, Per; Granville, Andrew; Shallit, Jeffrey; Yu, Sheng 1 1994 Inclusion is undecidable for pattern languages. Zbl 1422.68152 Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng 10 1993 Limited nondeterminism for pushdown automata. Zbl 1023.68621 Salomaa, Kai; Yu, Sheng 9 1993 Structural equivalence and ET0L grammars. Zbl 0794.68093 Salomaa, Kai; Wood, Derick; Yu, Sheng 4 1993 Decidability of the intercode property. Zbl 0824.68061 Jürgensen, H.; Salomaa, K.; Yu, S. 4 1993 Characterizing regular languages with polynomial densities. Zbl 1493.68195 Szilard, Andrew; Yu, Sheng; Zhang, Kaizhong; Shallit, Jeffrey 22 1992 Decidability of structural equivalence of E0L grammars. Zbl 0729.68039 Salomaa, Kai; Yu, Sheng 6 1991 Primality types of instances of the Post correspondence problem. Zbl 0744.68083 Salomaa, Arto; Salomaa, Kai; Yu, Sheng 5 1991 Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems. Zbl 0743.68085 Culik, Karel II.; Yu, Sheng 5 1991 Degrees of nondeterminism for pushdown automata. Zbl 0925.03175 Salomaa, Kai; Yu, Sheng 3 1991 ...and 12 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 802 Authors 71 Salomaa, Kai T. 52 Yu, Sheng 36 Kutrib, Martin 33 Holzer, Markus 32 Salomaa, Arto Kustaa 30 Jirásková, Galina 28 Han, Yo-Sub 21 Okhotin, Alexander 21 Reidenbach, Daniel 20 Brzozowski, Janusz Antoni 19 Teh, Wen Chean 17 Kari, Lila 16 Moreira, Nelma 15 Ko, Sang-Ki 15 Reis, Rogério 15 Subramanian, Kumbakonam Govindarajan 14 Ng, Timothy 13 Caron, Pascal 12 Champarnaud, Jean-Marc 12 Shallit, Jeffrey Outlaw 11 Freydenberger, Dominik D. 11 Gruber, Hermann 11 Manea, Florin 11 Pighizzini, Giovanni 11 Qiu, Daowen 11 Schmid, Markus L. 10 Atanasiu, Adrian 10 Gao, Yuan 10 Malcher, Andreas 9 Broda, Sabine 9 Culik, Karel II 9 Fernau, Henning 9 Hoffmann, Stefan 9 Hospodár, Michal 9 Ipate, Florentin 9 Kari, Jarkko 9 Margara, Luciano 9 Szykuła, Marek 9 Wendlandt, Matthias 9 Wood, Derick 8 Bera, Somnath 8 Ćirić, Miroslav D. 8 Domaratzki, Michael 8 Formenti, Enrico 8 Geffert, Viliam 8 Gruska, Jozef 8 Li, Lvzhou 8 Luque, Jean-Gabriel 8 Mahalingam, Kalpana 8 Mateescu, Alexandru 8 Mignot, Ludovic 8 Poovanandran, Ghajendran 8 Rappaport, David 8 Šebej, Juraj 8 Zheng, Shenggen 7 Cattaneo, Gianpiero 7 Dassow, Jürgen 7 Gheorghe, Marian 7 Ibarra, Oscar H. 7 Karhumaki, Juhani 7 Machiavelo, António 6 Calude, Cristian S. 6 Câmpeanu, Cezar 6 Ignjatović, Jelena 6 Ilie, Lucian 6 Mathew, Lisa 6 Mitrana, Victor 6 Nagar, Atulya K. 6 Patrou, Bruno 6 Piao, Xiaoxue 5 Černý, Anton 5 Cho, Da-Jung 5 Day, Joel D. 5 Fazekas, Szilárd Zsolt 5 Jakobi, Sebastian 5 Kosche, Maria 5 Koss, Tore 5 Lange, Steffen 5 Manzini, Giovanni 5 Mereghetti, Carlo 5 Palano, Beatrice 5 Palioudakis, Alexandros 5 Păun, Gheorghe 5 Schneider, Johannes C. 5 Siemer, Stefan 5 Verlan, Sergey 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 Flocchini, Paola 4 Garcia, Pedro 4 Guingne, Franck 4 Hunt, Harry Bowen III 4 Jiang, Tao 4 Konur, Savas 4 Kůrka, Petr ...and 702 more Authors all top 5 Cited in 88 Serials 227 Theoretical Computer Science 93 International Journal of Foundations of Computer Science 46 Information and Computation 29 Journal of Computer and System Sciences 20 Discrete Applied Mathematics 18 Acta Informatica 18 Information Processing Letters 18 Physica D 13 Natural Computing 12 RAIRO. Theoretical Informatics and Applications 9 Information Sciences 9 International Journal of Computer Mathematics 9 Theory of Computing Systems 8 Fuzzy Sets and Systems 8 Journal of Automata, Languages and Combinatorics 7 RAIRO. Theoretical Informatics and Applications 5 RAIRO. Informatique Théorique et Applications 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 Fundamenta Informaticae 2 Journal of Systems Science and Complexity 2 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 2 Logical Methods in Computer Science 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 International Journal of Control 1 Israel Journal of 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 Journal de Théorie des Nombres de Bordeaux 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 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 Ars Mathematica Contemporanea 1 Journal of Applied Mathematics & Informatics 1 Frontiers of Computer Science in China 1 Computer Science Review 1 Proceedings of the American Mathematical Society. Series B 1 Advances in Combinatorics all top 5 Cited in 27 Fields 804 Computer science (68-XX) 49 Dynamical systems and ergodic theory (37-XX) 35 Mathematical logic and foundations (03-XX) 35 Combinatorics (05-XX) 27 Group theory and generalizations (20-XX) 21 Information and communication theory, circuits (94-XX) 14 Number theory (11-XX) 12 Quantum theory (81-XX) 11 Biology and other natural sciences (92-XX) 10 Operations research, mathematical programming (90-XX) 6 Linear and multilinear algebra; matrix theory (15-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Associative rings and algebras (16-XX) 3 Statistical mechanics, structure of matter (82-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Systems theory; control (93-XX) 2 General and overarching topics; collections (00-XX) 2 History and biography (01-XX) 2 Probability theory and stochastic processes (60-XX) 1 Field theory and polynomials (12-XX) 1 Commutative algebra (13-XX) 1 Algebraic geometry (14-XX) 1 Measure and integration (28-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 Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.