 | 2009 |
|---|
| 111 |       | Yo-Sub Han,
Kai Salomaa,
Derick Wood:
Operational State Complexity of Prefix-Free Regular Languages.
Automata, Formal Languages, and Related Topics 2009: 99-115 |
| 110 |  | Adam Clarridge,
Kai Salomaa:
A Cellular Automaton Model for Car Traffic with a Slow-to-Stop Rule.
CIAA 2009: 44-53 |
| 109 | | Adam Clarridge,
Kai Salomaa:
A Cryptosystem Based on the Composition of Reversible Cellular Automata.
LATA 2009: 314-325 |
| 108 | | Yo-Sub Han,
Kai Salomaa,
Sheng Yu:
State Complexity of Combined Operations for Prefix-Free Regular Languages.
LATA 2009: 398-409 |
| 107 | | Kai Salomaa:
State Complexity of Nested Word Automata.
LATA 2009: 59-70 |
| 106 | | Mark Daley,
Michael Domaratzki,
Kai Salomaa:
State complexity of orthogonal catenation
CoRR abs/0904.3366: (2009) |
| 105 | | Yo-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) |
| 104 | | Arto Salomaa,
Kai Salomaa,
Sheng Yu:
Variants of codes and indecomposable languages.
Inf. Comput. 207(11): 1340-1349 (2009) |
| 103 | | Yo-Sub Han,
Kai Salomaa:
State complexity of basic operations on suffix-free regular languages.
Theor. Comput. Sci. 410(27-29): 2537-2548 (2009) |
| 102 | | Yo-Sub Han,
Kai Salomaa:
Nondeterministic state complexity of nested word automata.
Theor. Comput. Sci. 410(30-32): 2961-2971 (2009) |
| 101 | | Franziska Biegler,
Kai Salomaa:
On the synchronized derivation depth of context-free grammars.
Theor. Comput. Sci. 410(35): 3198-3208 (2009) |
| 100 | | Elena Czeizler,
Eugen Czeizler,
Lila Kari,
Kai Salomaa:
On the descriptional complexity of Watson-Crick automata.
Theor. Comput. Sci. 410(35): 3250-3260 (2009) |
| 99 | | Xiaoxue Piao,
Kai Salomaa:
Operational state complexity of nested word automata.
Theor. Comput. Sci. 410(35): 3290-3302 (2009) |
| 98 | | Kai Salomaa,
Sheng Yu,
Jinfeng Zan:
Deciding determinism of caterpillar expressions.
Theor. Comput. Sci. 410(37): 3438-3446 (2009) |
| 2008 |
|---|
| 97 | | Kai Salomaa:
Language Decompositions, Primality, and Trajectory-Based Operations.
CIAA 2008: 17-22 |
| 96 | | Arto Salomaa,
Kai Salomaa,
Sheng Yu:
Length Codes, Products of Languages and Primality.
LATA 2008: 476-486 |
| 95 | | Yuan 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) |
| 94 | | Yo-Sub Han,
Kai Salomaa:
State Complexity of Union and Intersection of Finite Languages.
Int. J. Found. Comput. Sci. 19(3): 581-595 (2008) |
| 93 | | Michael Domaratzki,
Kai Salomaa:
Preface.
Int. J. Found. Comput. Sci. 19(5): 1085-1086 (2008) |
| 92 | | Michael Domaratzki,
Kai Salomaa:
Lower bounds for the transition complexity of NFAs.
J. Comput. Syst. Sci. 74(7): 1116-1130 (2008) |
| 2007 |
|---|
| 91 | | Kai Salomaa,
Sheng Yu,
Jinfeng Zan:
Deterministic Caterpillar Expressions.
CIAA 2007: 97-108 |
| 90 | | Yo-Sub Han,
Kai Salomaa:
State Complexity of Union and Intersection of Finite Languages.
Developments in Language Theory 2007: 217-228 |
| 89 | | Kai Salomaa:
Descriptional Complexity of Nondeterministic Finite Automata.
Developments in Language Theory 2007: 31-35 |
| 88 | | Yo-Sub Han,
Kai Salomaa:
State Complexity of Basic Operations on Suffix-Free Regular Languages.
MFCS 2007: 501-512 |
| 87 | | Yo-Sub Han,
Kai Salomaa,
Derick Wood:
Intercode Regular Languages.
Fundam. Inform. 76(1-2): 113-128 (2007) |
| 86 | | Kai Salomaa,
Sheng Yu:
On the State Complexity of Combined Operations and their Estimation.
Int. J. Found. Comput. Sci. 18(4): 683-698 (2007) |
| 85 | | Kai Salomaa,
Paul Schofield:
State Complexity of Additive Weighted Finite Automata.
Int. J. Found. Comput. Sci. 18(6): 1407-1416 (2007) |
| 84 | | Yo-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) |
| 83 | | Arto Salomaa,
Kai Salomaa,
Sheng Yu:
State complexity of combined operations.
Theor. Comput. Sci. 383(2-3): 140-152 (2007) |
| 82 | | Franziska Biegler,
Ian McQuillan,
Kai Salomaa:
An infinite hierarchy induced by depth synchronization.
Theor. Comput. Sci. 387(2): 113-124 (2007) |
| 81 | | Brendan J. Cordy,
Kai Salomaa:
On the existence of regular approximations.
Theor. Comput. Sci. 387(2): 125-135 (2007) |
| 80 | | Michael Domaratzki,
Kai Salomaa:
Transition complexity of language operations.
Theor. Comput. Sci. 387(2): 147-154 (2007) |
| 2006 |
|---|
| 79 | | Ian McQuillan,
Kai Salomaa,
Mark Daley:
Iterated TGR Languages: Membership Problem and Effective Closure Properties.
COCOON 2006: 94-103 |
| 78 | | Yo-Sub Han,
Kai Salomaa,
Derick Wood:
Prime Decompositions of Regular Languages.
Developments in Language Theory 2006: 145-155 |
| 77 | | Michael Domaratzki,
Kai Salomaa:
Lower Bounds for the Transition Complexity of NFAs.
MFCS 2006: 315-326 |
| 76 | | Michael Domaratzki,
Grzegorz Rozenberg,
Kai Salomaa:
Interpreted Trajectories.
Fundam. Inform. 73(1-2): 81-97 (2006) |
| 75 | | Michael Domaratzki,
Kai Salomaa:
Codes defined by multiple sets of trajectories.
Theor. Comput. Sci. 366(3): 182-193 (2006) |
| 2005 |
|---|
| 74 | | Alexander Okhotin,
Kai Salomaa:
Contextual Grammars with Uniform Sets of Trajectories.
Fundam. Inform. 64(1-4): 341-351 (2005) |
| 73 | | Kai Salomaa,
Sheng Yu:
Preface.
Int. J. Found. Comput. Sci. 16(3): 399-401 (2005) |
| 72 | | Michael Domaratzki,
Kai Salomaa:
Restricted sets of trajectories and decidability of shuffle decompositions.
Int. J. Found. Comput. Sci. 16(5): 897-912 (2005) |
| 71 | | Michael 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 |
| 69 | | Michael Domaratzki,
Kai Salomaa:
Decidability of Trajectory-Based Equations.
MFCS 2004: 723-734 |
| 68 | | Kai 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 |
|---|
| 66 | | Cezar Câmpeanu,
Kai Salomaa,
Sheng Yu:
A Formal Study Of Practical Regular Expressions.
Int. J. Found. Comput. Sci. 14(6): 1007-1018 (2003) |
| 2002 |
|---|
| 65 | | Cezar Câmpeanu,
Kai Salomaa,
Sheng Yu:
Regex and Extended Regex.
CIAA 2002: 77-84 |
| 64 | | Alexander Okhotin,
Kai Salomaa,
Michael Domaratzki:
One-Visit Caterpillar Tree Automata.
Fundam. Inform. 52(4): 361-375 (2002) |
| 63 | | Cezar Câmpeanu,
Kai Salomaa,
Sándor Vágvölgyi:
Shuffle Decompositions of Regular Languages.
Int. J. Found. Comput. Sci. 13(6): 799-816 (2002) |
| 62 | | Cristian 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) |
| 61 | | Cristian 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) |
| 59 | | Kai Salomaa,
Sheng Yu:
Decidability of EDT0L structural equivalence.
Theor. Comput. Sci. 276(1-2): 245-259 (2002) |
| 2001 |
|---|
| 58 | | Cezar Câmpeanu,
Kai Salomaa,
Sándor Vágvölgyi:
Shuffle Quotient and Decompositions.
Developments in Language Theory 2001: 186-196 |
| 57 | | Alexandru 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) |
| 54 | | Kai Salomaa,
Xiuming Wu,
Sheng Yu:
Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata.
Theor. Comput. Sci. 231(1): 103-111 (2000) |
| 53 | | Kai 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 |
| 51 | | Cristian Calude,
Kai Salomaa,
Sheng Yu:
Metric Lexical Analysis.
WIA 1999: 48-59 |
| 50 | | Cezar Câmpeanu,
Karel Culik II,
Kai Salomaa,
Sheng Yu:
State Complexity of Basic Operations on Finite Languages.
WIA 1999: 60-70 |
| 49 | | Kai Salomaa,
Sheng Yu:
Generalized Fairness and Context-Free Languages.
Acta Cybern. 14(1): 193-204 (1999) |
| 48 | | Kai Salomaa,
Sheng Yu:
Synchronization Expressions and Languages.
J. UCS 5(9): 610-621 (1999) |
| 1998 |
|---|
| 47 | | Sandra 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) |
| 45 | | Kai 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) |
| 35 | | Kai 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) |
| 33 | | Kai Salomaa,
Derick Wood,
Sheng Yu:
Structural Equivalence and ET0L Grammars.
Theor. Comput. Sci. 164(1&2): 123-140 (1996) |
| 32 | | Kai 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) |
| 26 | | Alexandru 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 |
| 12 | | Kai 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) |
