×

Yu, Sheng (b. 1950 d. 2012)

Author ID: yu.sheng Recent zbMATH articles by "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

Publications by Year

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 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

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.