The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Kai Salomaa: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  83. Operational State Complexity of Prefix-Free Regular Languages. [Citation Graph (, )][DBLP]


  84. Hierarchies of synchronized and algebraic forests. [Citation Graph (, )][DBLP]


  85. Decidability of fairness for context-free languages. [Citation Graph (, )][DBLP]


  86. A Cellular Automaton Model for Car Traffic with a Slow-to-Stop Rule. [Citation Graph (, )][DBLP]


  87. Language Decompositions, Primality, and Trajectory-Based Operations. [Citation Graph (, )][DBLP]


  88. Length Codes, Products of Languages and Primality. [Citation Graph (, )][DBLP]


  89. A Cryptosystem Based on the Composition of Reversible Cellular Automata. [Citation Graph (, )][DBLP]


  90. State Complexity of Nested Word Automata. [Citation Graph (, )][DBLP]


  91. State Complexity of Combined Operations for Prefix-Free Regular Languages. [Citation Graph (, )][DBLP]


  92. State complexity of orthogonal catenation [Citation Graph (, )][DBLP]


  93. Transition Complexity of Incomplete DFAs [Citation Graph (, )][DBLP]


  94. Operational State Complexity of Deterministic Unranked Tree Automata [Citation Graph (, )][DBLP]


  95. Transformations Between Different Types of Unranked Bottom-Up Tree Automata [Citation Graph (, )][DBLP]


  96. Nondeterministic State Complexity for Suffix-Free Regular Languages [Citation Graph (, )][DBLP]


  97. Finite-State Complexity and the Size of Transducers [Citation Graph (, )][DBLP]


Search in 0.111secs, Finished in 0.114secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002