dblp.uni-trier.dewww.uni-trier.de

Kai Salomaa

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

2009
102EEAdam Clarridge, Kai Salomaa: A Cryptosystem Based on the Composition of Reversible Cellular Automata. LATA 2009: 314-325
101EEYo-Sub Han, Kai Salomaa, Sheng Yu: State Complexity of Combined Operations for Prefix-Free Regular Languages. LATA 2009: 398-409
100EEKai Salomaa: State Complexity of Nested Word Automata. LATA 2009: 59-70
99EEMark Daley, Michael Domaratzki, Kai Salomaa: State complexity of orthogonal catenation CoRR abs/0904.3366: (2009)
98EEYo-Sub Han, Kai Salomaa, Derick Wood: Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages. Fundam. Inform. 90(1-2): 93-106 (2009)
2008
97EEKai Salomaa: Language Decompositions, Primality, and Trajectory-Based Operations. CIAA 2008: 17-22
96EEArto Salomaa, Kai Salomaa, Sheng Yu: Length Codes, Products of Languages and Primality. LATA 2008: 476-486
95EEYuan Gao, Kai Salomaa, Sheng Yu: The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal. Fundam. Inform. 83(1-2): 75-89 (2008)
94EEYo-Sub Han, Kai Salomaa: State Complexity of Union and Intersection of Finite Languages. Int. J. Found. Comput. Sci. 19(3): 581-595 (2008)
93EEMichael Domaratzki, Kai Salomaa: Preface. Int. J. Found. Comput. Sci. 19(5): 1085-1086 (2008)
92EEMichael Domaratzki, Kai Salomaa: Lower bounds for the transition complexity of NFAs. J. Comput. Syst. Sci. 74(7): 1116-1130 (2008)
2007
91EEKai Salomaa, Sheng Yu, Jinfeng Zan: Deterministic Caterpillar Expressions. CIAA 2007: 97-108
90EEYo-Sub Han, Kai Salomaa: State Complexity of Union and Intersection of Finite Languages. Developments in Language Theory 2007: 217-228
89EEKai Salomaa: Descriptional Complexity of Nondeterministic Finite Automata. Developments in Language Theory 2007: 31-35
88EEYo-Sub Han, Kai Salomaa: State Complexity of Basic Operations on Suffix-Free Regular Languages. MFCS 2007: 501-512
87EEYo-Sub Han, Kai Salomaa, Derick Wood: Intercode Regular Languages. Fundam. Inform. 76(1-2): 113-128 (2007)
86EEKai Salomaa, Sheng Yu: On the State Complexity of Combined Operations and their Estimation. Int. J. Found. Comput. Sci. 18(4): 683-698 (2007)
85EEKai Salomaa, Paul Schofield: State Complexity of Additive Weighted Finite Automata. Int. J. Found. Comput. Sci. 18(6): 1407-1416 (2007)
84EEYo-Sub Han, Arto Salomaa, Kai Salomaa, Derick Wood, Sheng Yu: On the existence of prime decompositions. Theor. Comput. Sci. 376(1-2): 60-69 (2007)
83EEArto Salomaa, Kai Salomaa, Sheng Yu: State complexity of combined operations. Theor. Comput. Sci. 383(2-3): 140-152 (2007)
82EEFranziska Biegler, Ian McQuillan, Kai Salomaa: An infinite hierarchy induced by depth synchronization. Theor. Comput. Sci. 387(2): 113-124 (2007)
81EEBrendan J. Cordy, Kai Salomaa: On the existence of regular approximations. Theor. Comput. Sci. 387(2): 125-135 (2007)
80EEMichael Domaratzki, Kai Salomaa: Transition complexity of language operations. Theor. Comput. Sci. 387(2): 147-154 (2007)
2006
79EEIan McQuillan, Kai Salomaa, Mark Daley: Iterated TGR Languages: Membership Problem and Effective Closure Properties. COCOON 2006: 94-103
78EEYo-Sub Han, Kai Salomaa, Derick Wood: Prime Decompositions of Regular Languages. Developments in Language Theory 2006: 145-155
77EEMichael Domaratzki, Kai Salomaa: Lower Bounds for the Transition Complexity of NFAs. MFCS 2006: 315-326
76EEMichael Domaratzki, Grzegorz Rozenberg, Kai Salomaa: Interpreted Trajectories. Fundam. Inform. 73(1-2): 81-97 (2006)
75EEMichael Domaratzki, Kai Salomaa: Codes defined by multiple sets of trajectories. Theor. Comput. Sci. 366(3): 182-193 (2006)
2005
74EEAlexander Okhotin, Kai Salomaa: Contextual Grammars with Uniform Sets of Trajectories. Fundam. Inform. 64(1-4): 341-351 (2005)
73EEKai Salomaa, Sheng Yu: Preface. Int. J. Found. Comput. Sci. 16(3): 399-401 (2005)
72EEMichael Domaratzki, Kai Salomaa: Restricted sets of trajectories and decidability of shuffle decompositions. Int. J. Found. Comput. Sci. 16(5): 897-912 (2005)
71EEMichael Domaratzki, Kai Salomaa: Decidability of trajectory-based equations. Theor. Comput. Sci. 345(2-3): 304-330 (2005)
2004
70 Michael Domaratzki, Alexander Okhotin, Kai Salomaa, Sheng Yu: Implementation and Application of Automata, 9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers Springer 2004
69EEMichael Domaratzki, Kai Salomaa: Decidability of Trajectory-Based Equations. MFCS 2004: 723-734
68EEKai Salomaa, Derick Wood: Structural Equivalence of Regularly Extended E0L Grammars: An Automata Theoretic Proof. Theory Is Forever 2004: 259-267
67 Michael Domaratzki, Kai Salomaa: State Complexity of Shuffle on Trajectories. Journal of Automata, Languages and Combinatorics 9(2/3): 217-232 (2004)
2003
66EECezar Câmpeanu, Kai Salomaa, Sheng Yu: A Formal Study Of Practical Regular Expressions. Int. J. Found. Comput. Sci. 14(6): 1007-1018 (2003)
2002
65EECezar Câmpeanu, Kai Salomaa, Sheng Yu: Regex and Extended Regex. CIAA 2002: 77-84
64EEAlexander Okhotin, Kai Salomaa, Michael Domaratzki: One-Visit Caterpillar Tree Automata. Fundam. Inform. 52(4): 361-375 (2002)
63EECezar Câmpeanu, Kai Salomaa, Sándor Vágvölgyi: Shuffle Decompositions of Regular Languages. Int. J. Found. Comput. Sci. 13(6): 799-816 (2002)
62EECristian Calude, Kai Salomaa, Sheng Yu: Advances and Trends in Automata and Formal Languages A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen - J.UCS Special Issue. J. UCS 8(2): 117-118 (2002)
61EECristian Calude, Kai Salomaa, Sheng Yu: Additive Distances and Quasi-Distances Between Words. J. UCS 8(2): 141-152 (2002)
60 Cezar Câmpeanu, Kai Salomaa, Sheng Yu: Tight Lower Bound for the State Complexity of Shuffle of Regular Languages. Journal of Automata, Languages and Combinatorics 7(3): 303-310 (2002)
59EEKai Salomaa, Sheng Yu: Decidability of EDT0L structural equivalence. Theor. Comput. Sci. 276(1-2): 245-259 (2002)
2001
58EECezar Câmpeanu, Kai Salomaa, Sándor Vágvölgyi: Shuffle Quotient and Decompositions. Developments in Language Theory 2001: 186-196
57EEAlexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu: A sharpening of the Parikh mapping. ITA 35(6): 551-564 (2001)
56 Markus Holzer, Kai Salomaa, Sheng Yu: On the State Complexity of k-Entry Deterministic Finite Automata. Journal of Automata, Languages and Combinatorics 6(4): 453-466 (2001)
2000
55 Alexandru Mateescu, Kai Salomaa, Sheng Yu: On Fairness of Many-Dimensional Trajectories. Journal of Automata, Languages and Combinatorics 5(2): 145-158 (2000)
54EEKai Salomaa, Xiuming Wu, Sheng Yu: Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata. Theor. Comput. Sci. 231(1): 103-111 (2000)
53EEKai Salomaa, Sheng Yu: Alternating finite automata and star-free languages. Theor. Comput. Sci. 234(1-2): 167-176 (2000)
1999
52 Kai Salomaa, Sheng Yu: Synchronization Expressions: Characterization Results and Implementation. Jewels are Forever 1999: 45-56
51EECristian Calude, Kai Salomaa, Sheng Yu: Metric Lexical Analysis. WIA 1999: 48-59
50EECezar Câmpeanu, Karel Culik II, Kai Salomaa, Sheng Yu: State Complexity of Basic Operations on Finite Languages. WIA 1999: 60-70
49EEKai Salomaa, Sheng Yu: Generalized Fairness and Context-Free Languages. Acta Cybern. 14(1): 193-204 (1999)
48EEKai Salomaa, Sheng Yu: Synchronization Expressions and Languages. J. UCS 5(9): 610-621 (1999)
1998
47EESandra Huerter, Kai Salomaa, Xiuming Wu, Sheng Yu: Implementing Reversed Alternating Finite Automaton (r-AFA) Operations. Workshop on Implementing Automata 1998: 69-81
46 George Rahonis, Kai Salomaa: On the Size of Stack and Synchronization Alphabets of Tree Automata. Fundam. Inform. 36(1): 57-69 (1998)
45EEKai Salomaa, Sheng Yu: Synchronization Expressions with Extended Join Operation. Theor. Comput. Sci. 207(1): 73-88 (1998)
1997
44 Helmut Jürgensen, Kai Salomaa: Block-Synchronization Context-Free Grammars. Advances in Algorithms, Languages, and Complexity 1997: 111-137
43 Alexandru Mateescu, Kai Salomaa, Sheng Yu: Decidability of fairness for context-free languages. Developments in Language Theory 1997: 351-364
42 George Rahonis, Kai Salomaa: Hierarchies of synchronized and algebraic forests. Developments in Language Theory 1997: 447-460
41 Kai Salomaa, Sheng Yu: Rewriting Rules for Synchronization Languages. Structures in Logic and Computer Science 1997: 322-338
40 Kai Salomaa, Xiuming Wu, Sheng Yu: Efficient Implementation of Regular Languages Using R-AFA. Workshop on Implementing Automata 1997: 176-184
39 Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa: Semantics of Nonsequential Tree-Based Computation Schemes. Fundam. Inform. 29(4): 305-324 (1997)
38 Kai Salomaa, Sheng Yu: NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets. Journal of Automata, Languages and Combinatorics 2(3): 177-186 (1997)
1996
37 Kai Salomaa, Sheng Yu: NFA to DFA Transformation for Finite Languages. Workshop on Implementing Automata 1996: 149-158
36 L. Guo, Kai Salomaa, Sheng Yu: On Synchronization Languages. Fundam. Inform. 25(3): 423-436 (1996)
35EEKai Salomaa: Yield-Languages of Two-Way Pushdown Tree Automata. Inf. Process. Lett. 58(4): 195-199 (1996)
34 Kai Salomaa: On the Modularity of Decidability of Completeness and Termination. Journal of Automata, Languages and Combinatorics 1(1): 37-54 (1996)
33EEKai Salomaa, Derick Wood, Sheng Yu: Structural Equivalence and ET0L Grammars. Theor. Comput. Sci. 164(1&2): 123-140 (1996)
32EEKai Salomaa: Decidability of Equivalence for Deterministic Synchronized Tree Automata. Theor. Comput. Sci. 167(1&2): 171-192 (1996)
1995
31 Kai Salomaa, Sheng Yu: Nondeterminism Degrees for Context-Free Languages. Developments in Language Theory 1995: 154-165
30 Kai Salomaa: Decidability of Equivalence for Deterministic Synchronized Tree Automata. TAPSOFT 1995: 140-154
29 Kai Salomaa, Derick Wood, Sheng Yu: Complexity of E0L Structural Equivalence. ITA 29(6): 471-485 (1995)
28 Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu: P, NP and the Post Correspondence Problem Inf. Comput. 121(2): 135-142 (1995)
27 Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu: Decision Problems for Patterns. J. Comput. Syst. Sci. 50(1): 53-63 (1995)
26EEAlexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu: Lexical Analysis with a Simple Finite-Fuzzy-Automaton Model. J. UCS 1(5): 292-311 (1995)
1994
25 Kai Salomaa, Derick Wood, Sheng Yu: Complexity of E0L Structural Equivalence. MFCS 1994: 587-596
24 Kai Salomaa, Derick Wood, Sheng Yu: Rediscovering Pushdown Machines. Results and Trends in Theoretical Computer Science 1994: 372-385
23 Kai Salomaa, Derick Wood, Sheng Yu: Pumping and Pushdown Machines. ITA 28(3-4): 221-232 (1994)
22 Kai Salomaa, Sheng Yu: Measures of Nondeterminism for Pushdown Automata. J. Comput. Syst. Sci. 49(2): 362-374 (1994)
21 Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa: Semantics of Trees. Mathematical Systems Theory 27(2): 159-181 (1994)
20 Sheng Yu, Qingyu Zhuang, Kai Salomaa: The State Complexities of Some Basic Operations on Regular Languages. Theor. Comput. Sci. 125(2): 315-328 (1994)
19 Kai Salomaa: Synchronized Tree Automata. Theor. Comput. Sci. 127(1): 25-51 (1994)
18 Helmut Jürgensen, Kai Salomaa, Sheng Yu: Transducers and the Decidability of Independence in Free Monoids. Theor. Comput. Sci. 134(1): 107-117 (1994)
1993
17 Kai Salomaa, Derick Wood, Sheng Yu: Structural Equivalences and ET0L Grammars (Extended Abstract). FCT 1993: 430-439
16 Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu: Inclusion is Undecidable for Pattern Languages. ICALP 1993: 301-312
15 Kai Salomaa, Sheng Yu: Morphisms and rational tranducers. Bulletin of the EATCS 50: 186-193 (1993)
14 Helmut Jürgensen, Kai Salomaa, Sheng Yu: Decidability of the Intercode Property. Elektronische Informationsverarbeitung und Kybernetik 29(6): 375-380 (1993)
1992
13 Sheng Yu, Qingyu Zhuang, Kai Salomaa: Obtaining Tight Upper Bounds for the State Complexities of DFA Operations. ICCI 1992: 100-104
12EEKai Salomaa: Alternation Bounds for Tree Automata. Acta Cybern. 10(3): 173-198 (1992)
11 Kai Salomaa: Confluence, ground confluence, and termination of monadic term rewriting systems. Elektronische Informationsverarbeitung und Kybernetik 28(5): 279-309 (1992)
1991
10 Kai Salomaa, Sheng Yu: Degrees of Nondeterminism for Pushdown Automata. FCT 1991: 380-389
9 Kai Salomaa: Decidability of Confluence and Termination of Monadic Term Rewriting Systems. RTA 1991: 275-286
8 Arto Salomaa, Kai Salomaa, Sheng Yu: Primary Types of Instances of the Post Correspondence Problem. Bulletin of the EATCS 44: 226-241 (1991)
7 Kai Salomaa, Sheng Yu: Decidability of Structural Equivalence of E0L Grammars. Theor. Comput. Sci. 82(1): 131-139 (1991)
1990
6 Kai Salomaa, Sheng Yu: The Immortality Problem for LAG Systems. Inf. Process. Lett. 36(6): 311-315 (1990)
1989
5 Kai Salomaa: Representation of Recursively Enumerable Languages Using Alternating Finite Tree Recognizers. FCT 1989: 372-383
1988
4 Kai Salomaa: Yield-Languages Recognized by Alternating Tree Recognizers. ITA 22(3): 319-339 (1988)
3 Kai Salomaa: Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems. J. Comput. Syst. Sci. 37(3): 367-394 (1988)
1986
2 Kai Salomaa: Alternating Bottom-Up Tree Recognisers. CAAP 1986: 158-171
1984
1 H. C. M. Kleijn, Martti Penttonen, Grzegorz Rozenberg, Kai Salomaa: Direction Independent Context-Sensitive Grammars Information and Control 63(1/2): 113-117 (1984)

Coauthor Index

1Franziska Biegler [82]
2Cristian S. Calude (Cristian Calude) [51] [61] [62]
3Cezar Câmpeanu [50] [58] [60] [63] [65] [66]
4Adam Clarridge [102]
5Brendan J. Cordy [81]
6Karel Culik II [50]
7Mark Daley [79] [99]
8Michael Domaratzki [64] [67] [69] [70] [71] [72] [75] [76] [77] [80] [92] [93] [99]
9Andrzej Ehrenfeucht [21] [39]
10Yuan Gao [95]
11L. Guo [36]
12Yo-Sub Han [78] [84] [87] [88] [90] [94] [98] [101]
13Markus Holzer [56]
14Sandra Huerter [47]
15Tao Jiang [16] [27]
16Helmut Jürgensen [14] [18] [44]
17Jetty Kleijn (H. C. M. Kleijn) [1]
18Alexandru Mateescu [26] [28] [43] [55] [57]
19Ian McQuillan [79] [82]
20Alexander Okhotin [64] [70] [74]
21Martti Penttonen [1]
22George Rahonis [42] [46]
23Grzegorz Rozenberg [1] [21] [39] [76]
24Arto Salomaa [8] [16] [26] [27] [28] [57] [83] [84] [96]
25Paul Schofield [85]
26Sándor Vágvölgyi [58] [63]
27Derick Wood [17] [23] [24] [25] [29] [33] [68] [78] [84] [87] [98]
28Xiuming Wu [40] [47] [54]
29Sheng Yu [6] [7] [8] [10] [13] [14] [15] [16] [17] [18] [20] [22] [23] [24] [25] [26] [27] [28] [29] [31] [33] [36] [37] [38] [40] [41] [43] [45] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [59] [60] [61] [62] [65] [66] [70] [73] [83] [84] [86] [91] [95] [96] [101]
30Jinfeng Zan [91]
31Qingyu Zhuang [13] [20]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)