×

zbMATH — the first resource for mathematics

Salomaa, Kai T.

Compute Distance To:
Author ID: salomaa.kai-t Recent zbMATH articles by "Salomaa, Kai T."
Published as: Salomaa, K.; Salomaa, Kai; Salomaa, Kai T.
External Links: MGP · Wikidata · dblp · GND
Documents Indexed: 222 Publications since 1984, including 5 Books

Publications by Year

Citations contained in zbMATH

135 Publications have been cited 828 times in 429 Documents Cited by Year
The state complexities of some basic operations on regular languages. Zbl 0795.68112
Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai
107
1994
A sharpening of the Parikh mapping. Zbl 1005.68092
Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
53
2001
State complexity of combined operations. Zbl 1124.68056
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
35
2007
Decision problems for patterns. Zbl 0827.68066
Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
32
1995
A formal study of practical regular expressions. Zbl 1101.68443
Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng
27
2003
State complexity of basic operations on finite languages. Zbl 1050.68091
Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng
24
2001
Pattern languages with and without erasing. Zbl 0939.68690
Jiang, Tao; Kinber, Efim; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
24
1994
State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033
Han, Yo-Sub; Salomaa, Kai
23
2009
Deterministic tree pushdown automata and monadic tree rewriting systems. Zbl 0668.68084
Salomaa, Kai
23
1988
Tight lower bound for the state complexity of shuffle of regular languages. Zbl 1033.68057
Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng
22
2002
NFA to DFA transformation for finite languages over arbitrary alphabets. Zbl 0897.68060
Salomaa, Kai; Yu, Sheng
17
1997
Operational state complexity of nested word automata. Zbl 1176.68108
Piao, Xiaoxue; Salomaa, Kai
15
2009
The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040
Gao, Yuan; Salomaa, Kai; Yu, Sheng
15
2008
On the state complexity of combined operations and their estimations. Zbl 1149.68397
Salomaa, Kai; Zu, Sheng
15
2007
On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093
Holzer, Markus; Salomaa, Kai; Yu, Sheng
14
2001
Nondeterministic state complexity of nested word automata. Zbl 1173.68034
Han, Yo-Sub; Salomaa, Kai
13
2009
Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 0960.68611
Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai
13
1995
Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
12
2009
Operational state complexity of prefix-free regular languages. Zbl 1182.68105
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
11
2009
State complexity of union and intersection of finite languages. Zbl 1155.68037
Han, Yo-Sub; Salomaa, Kai
10
2008
On the existence of prime decompositions. Zbl 1111.68055
Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng
10
2007
Decidability of trajectory-based equations. Zbl 1079.68049
Domaratzki, Michael; Salomaa, Kai
9
2005
Additive distances and quasi-distances between words. Zbl 1258.68074
Calude, Cristian S.; Salomaa, Kai; Yu, Sheng
9
2002
The edit-distance between a regular language and a context-free language. Zbl 1293.68187
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
8
2013
Undecidability of the state complexity of composed regular operations. Zbl 1330.68179
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
8
2011
Patterns. Zbl 1089.68059
Salomaa, Kai
7
2004
Inclusion is undecidable for pattern languages. Zbl 1422.68152
Jiang, Tao; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
7
1993
State complexity of operations on input-driven pushdown automata. Zbl 1370.68186
Okhotin, Alexander; Salomaa, Kai
6
2017
Transition complexity of incomplete DFAs. Zbl 1230.68130
Gao, Yuan; Salomaa, Kai; Yu, Sheng
6
2011
Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235
Piao, Xiaoxue; Salomaa, Kai
6
2011
State complexity of operations on input-driven pushdown automata. Zbl 1343.68147
Okhotin, Alexander; Salomaa, Kai
6
2011
On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169
Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai
6
2009
State complexity of additive weighted finite automata. Zbl 1183.68354
Salomaa, Kai; Schofield, Paul
6
2007
Codes defined by multiple sets of trajectories. Zbl 1154.68066
Domaratzki, Michael; Salomaa, Kai
6
2006
Shuffle decompositions of regular languages. Zbl 1067.68085
Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S.
6
2002
Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111
Okhotin, Alexander; Salomaa, Kai
5
2015
Lower bounds for the transition complexity of NFAs. Zbl 1152.68028
Domaratzki, Michael; Salomaa, Kai
5
2008
Transition complexity of language operations. Zbl 1143.68033
Domaratzki, Michael; Salomaa, Kai
5
2007
Descriptional complexity of nondeterministic finite automata. Zbl 1202.68239
Salomaa, Kai
5
2007
Transducers and the decidability of independence in free monoids. Zbl 0938.68710
Jürgensen, H.; Salomaa, K.; Yu, S.
5
1994
Measures of nondeterminism for pushdown automata. Zbl 0822.68070
Salomaa, Kai; Yu, Sheng
5
1994
Limited nondeterminism for pushdown automata. Zbl 1023.68621
Salomaa, Kai; Yu, Sheng
5
1993
Decidability of structural equivalence of E0L grammars. Zbl 0729.68039
Salomaa, Kai; Yu, Sheng
5
1991
Primality types of instances of the Post correspondence problem. Zbl 0744.68083
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
5
1991
Quasi-distances and weighted finite automata. Zbl 1432.68239
Ng, Timothy; Rappaport, David; Salomaa, Kai
4
2015
Finite state complexity. Zbl 1235.68088
Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K.
4
2011
Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136
Salomaa, Kai
4
2011
State complexity of shuffle on trajectories. Zbl 1098.68068
Domaratzki, Michael; Salomaa, Kai
4
2004
On fairness of many-dimensional trajectories. Zbl 0959.68068
Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng
4
2000
Synchronized tree automata. Zbl 0805.68084
Salomaa, Kai
4
1994
Decidability of the intercode property. Zbl 0824.68061
Jürgensen, H.; Salomaa, K.; Yu, S.
4
1993
Edit distance neighbourhoods of input-driven pushdown automata. Zbl 06763511
Okhotin, Alexander; Salomaa, Kai
3
2017
State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096
Ng, Timothy; Rappaport, David; Salomaa, Kai
3
2015
Pseudo-inversion on formal languages. Zbl 1445.68121
Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai
3
2014
Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224
Okhotin, Alexander; Salomaa, Kai
3
2014
State complexity of the concatenation of regular tree languages. Zbl 1238.68079
Piao, Xiaoxue; Salomaa, Kai
3
2012
State trade-offs in unranked tree automata. Zbl 1341.68106
Piao, Xiaoxue; Salomaa, Kai
3
2011
Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141
Daley, M.; Domaratzki, M.; Salomaa, K.
3
2010
Prime decompositions of regular languages. Zbl 1227.68057
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
3
2006
Restricted sets of trajectories and decidability of shuffle decompositions. Zbl 1080.68053
Domaratzki, Michael; Salomaa, Kai
3
2005
Alternating finite automata and star-free languages. Zbl 0944.68090
Salomaa, K.; Yu, S.
3
2000
Block-synchronization context-free grammars. Zbl 0867.68077
Jürgensen, Helmut; Salomaa, Kai
3
1997
Lexical analysis with a simple finite-fuzzy-automaton model. Zbl 1044.68660
Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
3
1996
On synchronization languages. Zbl 0843.68055
Guo, L.; Salomaa, K.; Yu, S.
3
1996
Structural equivalence and ET0L grammars. Zbl 0794.68093
Salomaa, Kai; Wood, Derick; Yu, Sheng
3
1993
State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159
Ng, Timothy; Rappaport, David; Salomaa, Kai
2
2018
Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050
Kouhestani, Bahram; Rappaport, David; Salomaa, Kai
2
2018
Descriptional complexity of error detection. Zbl 1396.68068
Ng, Timothy; Rappaport, David; Salomaa, Kai
2
2017
The quotient operation on input-driven pushdown automata. Zbl 1426.68153
Okhotin, Alexander; Salomaa, Kai
2
2017
State complexity of insertion. Zbl 1404.68069
Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai
2
2016
Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317
Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai
2
2016
State complexity of deletion and bipolar deletion. Zbl 1335.68121
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
2
2016
State complexity of prefix distance. Zbl 1371.68160
Ng, Timothy; Rappaport, David; Salomaa, Kai
2
2015
Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
2
2013
Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176
Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai
2
2012
State-size hierarchy for finite-state complexity. Zbl 1283.68191
Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K.
2
2012
State complexity of Kleene-star operations on trees. Zbl 1353.68171
Piao, Xiaoxue; Salomaa, Kai
2
2012
Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172
Okhotin, Alexander; Salomaa, Kai
2
2011
Analysis of a cellular automaton model for car traffic with a slow-to-stop rule. Zbl 1207.68212
Clarridge, Adam; Salomaa, Kai
2
2010
An improved cellular automata based algorithm for the 45-convex hull problem. Zbl 1182.68132
Clarridge, Adam G.; Salomaa, Kai
2
2010
Variants of codes and indecomposable languages. Zbl 1192.68423
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
2
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 of nested word automata. Zbl 1234.68238
Salomaa, Kai
2
2009
State complexity of basic operations on suffix-free regular languages. Zbl 1147.68559
Han, Yo-Sub; Salomaa, Kai
2
2007
On the existence of regular approximations. Zbl 1143.68032
Cordy, Brendan; Salomaa, Kai
2
2007
Intercode regular languages. Zbl 1111.68056
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
2
2007
Iterated TGR languages: membership problem and effective closure properties. Zbl 1162.68473
McQuillan, Ian; Salomaa, Kai; Daley, Mark
2
2006
Lower bounds for the transition complexity of NFAs (extended abstract). Zbl 1132.68441
Domaratzki, Michael; Salomaa, Kai
2
2006
Decidability of trajectory-based equations. Zbl 1097.68057
Domaratzki, Michael; Salomaa, Kai
2
2004
Shuffle quotient and decompositions. Zbl 1073.68664
Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S.
2
2002
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
Pumping and pushdown machines. Zbl 0883.68093
Salomaa, Kai; Wood, D.; Yu, Sheng
2
1994
Degrees of nondeterminism for pushdown automata. Zbl 0925.03175
Salomaa, Kai; Yu, Sheng
2
1991
Hierarchy of k-context-free languages. II. Zbl 0672.68039
Salomaa, Kai
2
1989
A pumping result for 2-context-free languages. Zbl 0662.68077
Salomaa, Kai
2
1988
Yield-languages recognized by alternating tree recognizers. Zbl 0656.68087
Salomaa, Kai
2
1988
State complexity of prefix distance of subregular languages. Zbl 1392.68219
Ng, Timothy; Rappaport, David; Salomaa, Kai
1
2017
Outfix-guided insertion. Zbl 1382.68133
Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai
1
2017
Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044
Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai
1
2017
State complexity of neighbourhoods and approximate pattern matching. Zbl 1387.68159
Ng, Timothy; Rappaport, David; Salomaa, Kai
2
2018
Routing in a polygonal terrain with the shortest beacon watchtower. Zbl 1396.65050
Kouhestani, Bahram; Rappaport, David; Salomaa, Kai
2
2018
State complexity of operations on input-driven pushdown automata. Zbl 1370.68186
Okhotin, Alexander; Salomaa, Kai
6
2017
Edit distance neighbourhoods of input-driven pushdown automata. Zbl 06763511
Okhotin, Alexander; Salomaa, Kai
3
2017
Descriptional complexity of error detection. Zbl 1396.68068
Ng, Timothy; Rappaport, David; Salomaa, Kai
2
2017
The quotient operation on input-driven pushdown automata. Zbl 1426.68153
Okhotin, Alexander; Salomaa, Kai
2
2017
State complexity of prefix distance of subregular languages. Zbl 1392.68219
Ng, Timothy; Rappaport, David; Salomaa, Kai
1
2017
Outfix-guided insertion. Zbl 1382.68133
Cho, Da-Jung; Han, Yo-Sub; Ng, Timothy; Salomaa, Kai
1
2017
Ambiguity, nondeterminism and state complexity of finite automata. Zbl 1389.68044
Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai
1
2017
State complexity of insertion. Zbl 1404.68069
Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai
2
2016
Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1336.68317
Ko, Sang-Ki; Han, Yo-Sub; Salomaa, Kai
2
2016
State complexity of deletion and bipolar deletion. Zbl 1335.68121
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
2
2016
Operational state complexity of unary NFAs with finite nondeterminism. Zbl 1332.68125
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
1
2016
Descriptional complexity of unambiguous input-driven pushdown automata. Zbl 1318.68111
Okhotin, Alexander; Salomaa, Kai
5
2015
Quasi-distances and weighted finite automata. Zbl 1432.68239
Ng, Timothy; Rappaport, David; Salomaa, Kai
4
2015
State complexity of neighbourhoods and approximate pattern matching. Zbl 1386.68096
Ng, Timothy; Rappaport, David; Salomaa, Kai
3
2015
State complexity of prefix distance. Zbl 1371.68160
Ng, Timothy; Rappaport, David; Salomaa, Kai
2
2015
Generalizations of code languages with marginal errors. Zbl 1434.68255
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
1
2015
State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1327.68155
Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai
1
2015
Pseudo-inversion on formal languages. Zbl 1445.68121
Cho, Da-Jung; Han, Yo-Sub; Kang, Shin-Dong; Kim, Hwee; Ko, Sang-Ki; Salomaa, Kai
3
2014
Input-driven pushdown automata with limited nondeterminism (invited paper). Zbl 1425.68224
Okhotin, Alexander; Salomaa, Kai
3
2014
Nondeterministic state complexity of proportional removals. Zbl 1320.68110
Goč, Daniel; Palioudakis, Alexandros; Salomaa, Kai
1
2014
Unary NFAs with limited nondeterminism. Zbl 1432.68242
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
1
2014
State complexity of unary language operations for NFAs with limited nondeterminism. Zbl 1332.68124
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
1
2014
State complexity of inversion operations. Zbl 1332.68109
Cho, Da-Jung; Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
1
2014
The edit-distance between a regular language and a context-free language. Zbl 1293.68187
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
8
2013
Approximate matching between a context-free grammar and a finite-state automaton. Zbl 1298.68137
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
2
2013
Undecidability of state complexity. Zbl 1401.68167
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
1
2013
Comparisons between measures of nondeterminism on finite automata. Zbl 1388.68177
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
1
2013
State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. Zbl 1388.68168
Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai
1
2013
State complexity of the concatenation of regular tree languages. Zbl 1238.68079
Piao, Xiaoxue; Salomaa, Kai
3
2012
Descriptional complexity of input-driven pushdown automata. Zbl 1367.68176
Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai
2
2012
State-size hierarchy for finite-state complexity. Zbl 1283.68191
Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K.
2
2012
State complexity of Kleene-star operations on trees. Zbl 1353.68171
Piao, Xiaoxue; Salomaa, Kai
2
2012
State complexity of finite tree width NFAs. Zbl 1322.68126
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
1
2012
Cellular automaton based motion planning algorithms for mobile sensor networks. Zbl 1374.68309
Choudhury, Salimur; Salomaa, Kai; Akl, Selim G.
1
2012
State complexity and limited nondeterminism. Zbl 1304.68117
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
1
2012
Computing the edit-distance between a regular language and a context-free language. Zbl 1370.68171
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
1
2012
Undecidability of the state complexity of composed regular operations. Zbl 1330.68179
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
8
2011
Transition complexity of incomplete DFAs. Zbl 1230.68130
Gao, Yuan; Salomaa, Kai; Yu, Sheng
6
2011
Transformations between different models of unranked bottom-up tree automata. Zbl 1234.68235
Piao, Xiaoxue; Salomaa, Kai
6
2011
State complexity of operations on input-driven pushdown automata. Zbl 1343.68147
Okhotin, Alexander; Salomaa, Kai
6
2011
Finite state complexity. Zbl 1235.68088
Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K.
4
2011
Limitations of lower bound methods for deterministic nested word automata. Zbl 1230.68136
Salomaa, Kai
4
2011
State trade-offs in unranked tree automata. Zbl 1341.68106
Piao, Xiaoxue; Salomaa, Kai
3
2011
Descriptional complexity of unambiguous nested word automata. Zbl 1330.68172
Okhotin, Alexander; Salomaa, Kai
2
2011
Orthogonal concatenation: language equations and state complexity. Zbl 1216.68141
Daley, M.; Domaratzki, M.; Salomaa, K.
3
2010
Analysis of a cellular automaton model for car traffic with a slow-to-stop rule. Zbl 1207.68212
Clarridge, Adam; Salomaa, Kai
2
2010
An improved cellular automata based algorithm for the 45-convex hull problem. Zbl 1182.68132
Clarridge, Adam G.; Salomaa, Kai
2
2010
State complexity of basic operations on suffix-free regular languages. Zbl 1172.68033
Han, Yo-Sub; Salomaa, Kai
23
2009
Operational state complexity of nested word automata. Zbl 1176.68108
Piao, Xiaoxue; Salomaa, Kai
15
2009
Nondeterministic state complexity of nested word automata. Zbl 1173.68034
Han, Yo-Sub; Salomaa, Kai
13
2009
Nondeterministic state complexity of basic operations for prefix-free regular languages. Zbl 1161.68534
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
12
2009
Operational state complexity of prefix-free regular languages. Zbl 1182.68105
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
11
2009
On the descriptional complexity of Watson-Crick automata. Zbl 1180.68169
Czeizler, Elena; Czeizler, Eugen; Kari, Lila; Salomaa, Kai
6
2009
Variants of codes and indecomposable languages. Zbl 1192.68423
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
2
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 of nested word automata. Zbl 1234.68238
Salomaa, Kai
2
2009
A cryptosystem based on the composition of reversible cellular automata. Zbl 1234.94036
Clarridge, Adam; Salomaa, Kai
1
2009
The state complexity of two combined operations: star of catenation and star of reversal. Zbl 1147.68040
Gao, Yuan; Salomaa, Kai; Yu, Sheng
15
2008
State complexity of union and intersection of finite languages. Zbl 1155.68037
Han, Yo-Sub; Salomaa, Kai
10
2008
Lower bounds for the transition complexity of NFAs. Zbl 1152.68028
Domaratzki, Michael; Salomaa, Kai
5
2008
State complexity of combined operations. Zbl 1124.68056
Salomaa, Arto; Salomaa, Kai; Yu, Sheng
35
2007
On the state complexity of combined operations and their estimations. Zbl 1149.68397
Salomaa, Kai; Zu, Sheng
15
2007
On the existence of prime decompositions. Zbl 1111.68055
Han, Yo-Sub; Salomaa, Arto; Salomaa, Kai; Wood, Derick; Yu, Sheng
10
2007
State complexity of additive weighted finite automata. Zbl 1183.68354
Salomaa, Kai; Schofield, Paul
6
2007
Transition complexity of language operations. Zbl 1143.68033
Domaratzki, Michael; Salomaa, Kai
5
2007
Descriptional complexity of nondeterministic finite automata. Zbl 1202.68239
Salomaa, Kai
5
2007
State complexity of basic operations on suffix-free regular languages. Zbl 1147.68559
Han, Yo-Sub; Salomaa, Kai
2
2007
On the existence of regular approximations. Zbl 1143.68032
Cordy, Brendan; Salomaa, Kai
2
2007
Intercode regular languages. Zbl 1111.68056
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
2
2007
Deterministic caterpillar expressions. Zbl 1139.68374
Salomaa, Kai; Yu, Sheng; Zan, Jinfeng
1
2007
An infinite hierarchy induced by depth synchronization. Zbl 1143.68026
Biegler, Franziska; McQuillan, Ian; Salomaa, Kai
1
2007
State complexity of union and intersection of finite languages. Zbl 1202.68227
Han, Yo-Sub; Salomaa, Kai
1
2007
Codes defined by multiple sets of trajectories. Zbl 1154.68066
Domaratzki, Michael; Salomaa, Kai
6
2006
Prime decompositions of regular languages. Zbl 1227.68057
Han, Yo-Sub; Salomaa, Kai; Wood, Derick
3
2006
Iterated TGR languages: membership problem and effective closure properties. Zbl 1162.68473
McQuillan, Ian; Salomaa, Kai; Daley, Mark
2
2006
Lower bounds for the transition complexity of NFAs (extended abstract). Zbl 1132.68441
Domaratzki, Michael; Salomaa, Kai
2
2006
Interpreted trajectories. Zbl 1157.68380
Domaratzki, Michael; Rozenberg, Grzegorz; Salomaa, Kai
1
2006
Decidability of trajectory-based equations. Zbl 1079.68049
Domaratzki, Michael; Salomaa, Kai
9
2005
Restricted sets of trajectories and decidability of shuffle decompositions. Zbl 1080.68053
Domaratzki, Michael; Salomaa, Kai
3
2005
Patterns. Zbl 1089.68059
Salomaa, Kai
7
2004
State complexity of shuffle on trajectories. Zbl 1098.68068
Domaratzki, Michael; Salomaa, Kai
4
2004
Decidability of trajectory-based equations. Zbl 1097.68057
Domaratzki, Michael; Salomaa, Kai
2
2004
A formal study of practical regular expressions. Zbl 1101.68443
Câmpeanu, Cezar; Salomaa, Kai; Yu, Sheng
27
2003
Deletion on trajectories and commutative closure. Zbl 1040.68053
Domaratzki, Michael; Mateescu, Alexandru; 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
22
2002
Additive distances and quasi-distances between words. Zbl 1258.68074
Calude, Cristian S.; Salomaa, Kai; Yu, Sheng
9
2002
Shuffle decompositions of regular languages. Zbl 1067.68085
Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S.
6
2002
Shuffle quotient and decompositions. Zbl 1073.68664
Câmpeanu, C.; Salomaa, K.; Vágvölgyi, S.
2
2002
One-visit caterpillar tree automata. Zbl 1012.68102
Okhotin, Alexander; Salomaa, Kai; Domaratzki, Michael
1
2002
A sharpening of the Parikh mapping. Zbl 1005.68092
Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
53
2001
State complexity of basic operations on finite languages. Zbl 1050.68091
Câmpeanu, C.; Culik, K.; Salomaa, Kai; Yu, Sheng
24
2001
On the state complexity of \(k\)-entry deterministic finite automata. Zbl 1050.68093
Holzer, Markus; Salomaa, Kai; Yu, Sheng
14
2001
Metric lexical analysis. Zbl 1050.68090
Calude, Cristian S.; Salomaa, Kai; Yu, Sheng
1
2001
On fairness of many-dimensional trajectories. Zbl 0959.68068
Mateescu, Alexandru; Salomaa, Kai; Yu, Sheng
4
2000
Alternating finite automata and star-free languages. Zbl 0944.68090
Salomaa, K.; Yu, S.
3
2000
Efficient implementation of regular languages using reversed alternating finite automata. Zbl 0951.68061
Salomaa, K.; Wu, X.; Yu, S.
1
2000
Synchronization expressions and languages. Zbl 0960.68097
Salomaa, Kai; Yu, Sheng
1
1999
Synchronization expressions with extended join operation. Zbl 0912.68108
Salomaa, Kai; Yu, Sheng
2
1998
...and 35 more Documents
all top 5

Cited by 358 Authors

64 Salomaa, Kai T.
29 Yu, Sheng
28 Jirásková, Galina
28 Salomaa, Arto Kustaa
23 Kutrib, Martin
22 Han, Yo-Sub
21 Okhotin, Alexander
16 Brzozowski, Janusz Antoni
16 Holzer, Markus
16 Kari, Lila
15 Teh, Wen Chean
14 Reidenbach, Daniel
12 Ko, Sang-Ki
11 Domaratzki, Michael
11 Schmid, Markus L.
10 Freydenberger, Dominik D.
10 Gao, Yuan
10 Subramanian, Kumbakonam Govindarajan
9 Malcher, Andreas
9 Vágvölgyi, Sándor
8 Atanasiu, Adrian
8 Jirásek, Jozef jun.
8 Mateescu, Alexandru
8 Ng, Timothy
8 Šebej, Juraj
7 Bera, Somnath
7 Konstantinidis, Stavros
7 Mahalingam, Kalpana
6 Karhumaki, Juhani
6 McQuillan, Ian
6 Piao, Xiaoxue
6 Poovanandran, Ghajendran
6 Rappaport, David
6 Shallit, Jeffrey O.
6 Wood, Derick
5 Cui, Bo
5 Fernau, Henning
5 Hospodár, Michal
5 Jacquemard, Florent
5 Manea, Florin
5 Mlynárčik, Peter
5 Pighizzini, Giovanni
5 Schneider, Johannes C.
5 Wendlandt, Matthias
4 Bednárová, Zuzana
4 Biegler, Franziska
4 Câmpeanu, Cezar
4 Černý, Anton
4 Cho, Da-Jung
4 Eom, Hae-Sung
4 Geffert, Viliam
4 Lange, Steffen
4 Mereghetti, Carlo
4 Nagar, Atulya K.
4 Palano, Beatrice
4 Santean, Nicolae
4 Szykuła, Marek
3 Atanasiu, Radu-Florian
3 Caron, Pascal
3 Chatterjee, Kingshuk
3 Daley, Mark
3 Dassow, Jürgen
3 Davies, Sylvie
3 Day, Joel D.
3 Godoy, Guillem
3 Gruber, Hermann
3 Ibarra, Oscar H.
3 Jürgensen, Helmut
3 Kopecki, Steffen
3 Lipponen, Marjo
3 Liu, Guangwu
3 Luque, Jean-Gabriel
3 Mitrana, Victor
3 Otto, Friedrich
3 Palioudakis, Alexandros
3 Patrou, Bruno
3 Păun, Gheorghe
3 Ray, Kumar Sankar
3 Rigo, Michel
3 Rozenberg, Grzegorz
3 Seki, Shinnosuke
3 Sinnamon, Corwin W.
3 Staiger, Ludwig
3 Ye, Yuli
3 Zahedi, Mohammad Mehdi
3 Zeugmann, Thomas
2 Abdullah, Rosni
2 Alazemi, Hamed M. K.
2 Arimura, Hiroki
2 Asveld, Peter R. J.
2 Axelsen, Holger Bock
2 Bassino, Frédérique
2 Berglund, Martin
2 Björklund, Henrik
2 Calude, Cristian S.
2 Choffrut, Christian
2 Clerbout, Mireille
2 Ésik, Zoltán
2 Genet, Thomas
2 Ghorani, Maryam
...and 258 more Authors
all top 5

Cited in 43 Serials

146 Theoretical Computer Science
68 International Journal of Foundations of Computer Science
30 Information and Computation
18 Journal of Computer and System Sciences
14 Information Processing Letters
9 Theory of Computing Systems
7 Acta Informatica
6 Discrete Applied Mathematics
6 International Journal of Computer Mathematics
6 RAIRO. Informatique Théorique et Applications
6 RAIRO. Theoretical Informatics and Applications
5 Fuzzy Sets and Systems
4 Natural Computing
3 Formal Aspects of Computing
3 Soft Computing
3 RAIRO. Theoretical Informatics and Applications
2 Computational Geometry
2 Journal of Applied Mathematics and Computing
1 Acta Mathematica Vietnamica
1 Meccanica
1 Advances in Applied Mathematics
1 Bulletin of the Iranian Mathematical Society
1 Acta Mathematicae Applicatae Sinica. English Series
1 Journal of Symbolic Computation
1 Algorithmica
1 Journal of Automated Reasoning
1 International Journal of Approximate Reasoning
1 International Journal of Algebra and Computation
1 Indagationes Mathematicae. New Series
1 Applicable Algebra in Engineering, Communication and Computing
1 The Australasian Journal of Combinatorics
1 Russian Mathematics
1 Journal of Logic, Language and Information
1 Journal of the ACM
1 Discrete Mathematics and Theoretical Computer Science. DMTCS
1 Bulletin of the Malaysian Mathematical Sciences Society. Second Series
1 Iranian Journal of Fuzzy Systems
1 Mathematics in Computer Science
1 Algorithms
1 Statistics and Computing
1 Computer Science Review
1 Journal of Mathematics
1 Journal of Logical and Algebraic Methods in Programming

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.