九州大学大学院 システム情報科学研究院 情報理学部門
日本語 English
Department of Information ISEE, Kyushu University
トップ > 研究概要 > RIFIS Technical Report (No.1--No.123)
----
RIFIS Technical Report (No.1--No.123)

RIFIS Technical Report


  1. \Delta^{p}_{2}-complete lexicographically first maximal subgraph problems,
    S. Miyano, December, 1987 (Proc. Mathematical Foundations of Computer Science 1988, Lecture Notes in Computer Science 324, 454-462, 1988; Theoretical Computer Science 88 (1991) 33-57).
  2. Completeness of extended unification based on basic narrowing,
    A. Yamamoto, March, 1988 (Lecture Notes in Artificial Intelligence 383, 1-10, 1989).
  3. SIGMA: A text database management system,
    S. Arikawa et al., June, 1988 (Proc. Berliner Infromatik-Tage, 72-81, 1989).
  4. A reasoning system using inductive inference of analogical union,
    T. Miyahara, September, 1988 (Bulletin of Informatics and Cybernetics 23, 121-128, 1989).
  5. Pseudo extension in default reasoning and belief revision by model inference,
    H. Yuasa and S. Arikawa, October, 1988 (Lecture Notes in Artificial Intelligence 383,27-37, 1989).
  6. Parallel complexity and P-complete problems,
    S. Miyano, October, 1988 (Proc. International Conference on Fifth Generation Computer Systems 1988, 532-541)
  7. A proof of the correctness of Uratani's string searching algorithm,
    M. Takeda, October, 1988 (A fast string-searching algorithm for multiple patterns, to appear in Information Processing & Management).
  8. The lexicographically first topological order problem is NLOG-complete,
    T. Shoudai, December, 1988 (Information Processing Letters 33, 121-124, 1989).
  9. A parallel algorithm for the maximum 2-chain edge packing problem,
    S. Shiraishi, December, 1988 (Information Processing Letters 32, 277-279, 1989).
  10. T. Shinohara and S. Arikawa, Model inference using bidirectional refinements,
    Y. Kawasaki, December, 1988 (Bulletin of Informatics and Cybernetics 24, 1-14, 1990).
  11. A fast matching algorithm for patterns with pictures,
    M. Takeda, March, 1989.
  12. Elementary formal system as a logic programming language,
    A. Yamamoto, March, 1989 (Proc. Logic Programming Conference 1989, 123-132) .
  13. Efficient multiple string replacing with pictures,
    M. Takeda, March,1989 (Advances in Software Science and Technology 2, 131-151, 1990).
  14. Elementary formal system as a unifying framework for language learning,
    S. Arikawa, T. Shinohara and A. Yamamoto, March, 1989 (Proc. COLT'89, 312-327; Theoretical Computer Science 95, 97-113, 1992).
  15. Query processing for structured text as a relation,
    M. Takeda and T. Miyahara, March, 1989 (Information Modelling and Knowledge Bases, eds. Kangassalo et al., IOX Press, 483-492, 1990).
  16. A new series of \Delta^{p}_{2}-complete problems,
    S. Miyano, July, 1989 (Proc. Int. Workshop on Discrete Algorithms and Complexity, 1989, 187-194).
  17. A list of P-complete problems,
    S. Miyano, S. Shiraishi and T. Shoudai, October, 1989 (Revised: December, 1990).
  18. Completeness of diamond-resolution in or-type knowledge bases,
    H. Sakai, October, 1989 (Bulletin of Informatics and Cybernetics 24, 15-26, 1990).
  19. Time-bounded reasoning in first order knowledge base systems,
    Y. Shi and S. Arikawa, October, 1989 (Lecture Notes in Artificial Intelligence 485, 54-72, 1991).
  20. Inductive inference from positive data is powerful,
    T. Shinohara, November, 1989 (Proc. COLT'90, 97-110; to appear in Information and Computation).
  21. Completeness of depth-bounded resolution for weakly reducing programs,
    H. Arimura, December, 1989 (World Scientific Series in Computer Science, 31, 227--245,1991).
  22. A foundation of algorithmic teaching,
    A. Shinohara and S. Miyano, December, 1989.
  23. Decision problems for the intuitionistic logic without weakening rule,
    E. Kiriyama and H. Ono, March, 1990 (Studia Logica L,2, 299-319, 1991).
  24. Sufficiency of operators identification and inter-construction in inverting resolution,
    C. Zeng and S. Arikawa, April, 1990 (Bulletin of Informatics and Cybernetics 24, 111-120, 1991).
  25. Systematized approaches to the complexity of subgraph problems,
    S. Miyano, April, 1990 (J. Inform. Processing 13, 442-448, 1990).
  26. Teachability in computational learning,
    A. Shinohara and S. Miyano, April, 1990 (New Generation Computing 8, 337-347, 1991) .
  27. Bounded degree maximal subgraph problems are in NC,
    T. Shoudai and S. Miyano, July, 1990 (Proc. Toyohashi Symposium on Theoretical Computer Science, 97-101).
  28. Correct definition of finite elasticity,
    T. Motoki and T. Shinohara, April, 1990 (Proc. 4th Computational Learning Theory, 375-375, 1991).
  29. Inductive inference of monotonic formal systems from positive data,
    T. Shinohara, April, 1990 (Proc. ALT'90, 339-354; New Generation Computing 8, 371-384, 1991).
  30. Completeness of dynamic time-bounded derivation for locally weak reducing programs,
    Y. Shi and S. Arikawa, August, 1990 (Bulletin of Informatics and Cybernetics 24, 93-109, 1991).
  31. Depth-Bounded Inference for Nonterminating Prologs,
    H. Arimura, (Bulletin of Informatics and Cybernetics 25, 125--136, 1993) (Revised: May 14, 1993). (Former version: Termination properties of a subclass of ground I/O logic programs, October,1990)
  32. On maximum uniform partition of line graphs,
    S. Shiraishi, October, 1990.
  33. Finding optimal subgraphs by local search,
    S. Shimozono, December,1990 (Revised: August, 1992).
  34. O(log^{*}n) time parallel algorithm for computing bounded degree maximal subgraphs,
    T. Uchida and S. Miyano, January, 1991 (Transactions of Information Processing Society of Japan 34, 16-20, 1993).
  35. On Russellian propositions,
    K. Hirata, February, 1991 (Bulletin of Informatics and Cybernetics 25, 41-51, 1992).
  36. Using maximal independent sets to solve problems in parallel,
    T. Shoudai and S. Miyano, February, 1991 (Proc. 17th Intern. Workshop on Graph-Theoretic Concepts in Computer Science WG91, Lecture Notes in Computer Science 570, 126-134, 1991).
  37. Learning elementary formal systems and an application to discovering motifs in proteins,
    S. Miyano, A. Shinohara and T. Shinohara, (Proc. 2nd Workshop on Algorithmic Learning Theory, 139-150, 1991), (Revised: April, 1993). (Former version: Which classes of elementary formal systems are polynomial-time learnable, February, 1991)
  38. Analogy is NP-hard,
    S. Furuya and S. Miyano, March, 1991 (Proc. 2nd Workshop on Algorithmic Learning Theory, 207-212, 1991).
  39. NP-complete problems on label updating calculation in ATMS,
    S. Furuya and S. Miyano, March, 1991 (Bulletin of Informatics and Cybernetics 25, 1-6,1992).
  40. A Learning algorithm for elementary formal systems and its experiments on Identification of transmembrane domains,
    S. Arikawa, S. Kuhara, S. Miyano, A. Shinohara and T. Shinohara, June, 1991 (Proc. 25th Int.Conf. Hawaii International Conference on Information Systems, 675-684, 1992).
  41. Characterization of pattern languages,
    Y. Mukouchi, June, 1991 (Proc.2nd Workshop on Algorithmic Learning Theory, 93-104, 1991; IEICE Transactions on Information and Systems E75-D, 420-425, 1992).
  42. Relational graph rewritings,
    Y. Mizoguchi and Y. Kawahara, July, 1991 (to appear in Theoretical Computer Science A).
  43. Polynomial time inference of finite unions of tree pattern languages,
    H. Arimura, T. Shinohara and S. Otsuki, August, 1991 (IEICE Transactions on Information and Systems E75-D, 426-434, 1992; Proc. 2nd International Workshop on Nonmonotonic and Inductive Logic 1991 (Lecture Notes in Artificial Intelligence 659), 118-131, 1993).
  44. A machine discovery from amino acid sequences by decision trees over regular patterns,
    S. Arikawa, S. Kuhara, S. Miyano, Y. Mukouchi, A. Shinohara and T.Shinohara, August, 1991 (Revised: September, 1991; Proc. FGCS'92, 618-625, 1992; New Generation Computing 11, 361-375, 1993).
  45. A simple method of mutual translation between Japanese sentences and Horn clauses,
    H. Inoue, S. Arikawa, and S. Takeya, September, 1991.
  46. A P-complete langauge describable with iterated shuffle,
    T. Shoudai, September 6, 1991 (Information Processing Letters 41, 233-238, 1992).
  47. Sub-extensions and approximate extensions in Reiter's default logic,
    Y. Shi and S. Arikawa, September , 1991 (Bulletin of Informatics and Cybernetics 25, 7-20, 1992).
  48. Balanced formulas, BCK-minimal formulas and their proofs,
    S. Hirokawa, November, 1991 (Proc. Intern. Conf. on Logical Foundations of Computer Science, Lecture Notes in Computer Science 620, 198-208,1992).
  49. Degree-two formulas and their proofs,
    S. Hirokawa, November, 1991.
  50. Sub-extensions in the default knowledge base systems,
    Y. Shi and S. Arikawa, November, 1991.
  51. Inferring a tree from walks,
    O. Maruyama and S. Miyano, December, 1991 (Proc. 17th International Conference on Mathematical Foundation of Computer Science (Lecture Notes in Computer Science 629), 383-391, 1992; To appear in Theoretical Computer Science).
  52. Definite inductive inference as a successful identification criterion,
    Y. Mukouchi, December, 1991 (Proc. 3rd Intern. Workshop on Analogical and Inductive Inference (Lecture Notes in Artificial Intelligence 642), 260-267, 1992).
  53. A graph structure over the category of sets and partial functions,
    Y. Mizoguchi, January, 1992 (cahiers de topologie et g{\'e}nom{\'e}tries diff{\'e}entielle cat{\'e}goriques, Vol. 31-1, 2-12, 1993).
  54. On the characteristic numbers associated with two-dimensional cellular automata ca-90(m,n),
    Y.Kawahara, S.Kumamoto, Y.Mizoguchi, M.Nohmi, H.Ohtsuka and T.Shoudai, March, 1992.
  55. Incorporating explanation-based generalization with analogical reasoning,
    E. Hirowatari and S. Arikawa, March, 1992 (Proc. International Workshop on Inductive Logic Programming (ILP92), 1992), (Bulletin of Informatics and Cybernetics Vol. 26, 13-34, 1994).
  56. More about learning elementary formal systems,
    S. Arikawa, T. Shinohara, S. Miyano, A. Shinohara, March, 1992 (Proc. 2nd International Workshop on Nonmonotonic and Inductive Logics 1991 (Lecture Notes in Artificial Intelligence 659), 107-117, 1993).
  57. Algorithmic learning theory with elementary formal systems,
    S. Arikawa, S. Miyano, A. Shinohara, T. Shinohara, A. Yamamoto, March, 1992 (IEICE Transactions on Information and Systems E75-D, 405-414, 1992).
  58. Inductive inference with bounded mind changes,
    Y. Mukouchi, May, 1992 (Proc. 3rd Workshop on Algorithmic Learning Theory, 125-134, 1992).
  59. Parallel algorithms for refutation tree problem on formal graph systems,
    T. Uchida, T. Shoudai and S. Miyano, July, 1992 (Revised: April, 1993) (To appear in IEICE Transactions on Information and Systems).
  60. Finding alphabet indexing for decision trees over regular patterns: an approach to bioinformatical knowledge acquisition,
    S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara and S.Arikawa, August, 1992 (Proc. 26th Hawaii Int. Conf. System Sciences, 763-772, 1993).
  61. Complexity of finding alphabet indexing,
    S. Shimozono and S. Miyano, August, 1992.
  62. Stable model semantics of circumscription,
    K. Hirata, August, 1992 (Bulletin of Informatics and Cybernetics Vol. 26, 1-12, 1994).
  63. A generalization of the least general generalization,
    H. Arimura, H. Ishizaka, T. Shinohara and S. Otsuki, August, 1992 (To appear in Machine Intelligence, 13).
    p
  64. Attractivity in heteroassociative memory networks for image recognition,
    K. Niijima, October, 1992.
  65. A parallel algorithm for the maximal co-hitting set problem,
    T. Shoudai and S. Miyano, October, 1992 (IEICE Transactions on Information and Systems E76-D, No. 2, 296-298,1993).
  66. Approximating minimum common supertrees for complete k-ary trees,
    A. Yamaguchi and S. Miyano, March, 1993.
  67. Inductive inference machines that can refute hypothesis spaces,
    Y. Mukouchi and S.Arikawa, March, 1993 (Proc. 4th Intern. Workshop on Algorithmic Learning Theory (Lecture Notes in Artificial Intelligence 744), 123-136, 1993) (Revised: January, 1994).
  68. An NC algorithm for computing a maximal independent set in a hypergraph of bounded valence,
    T. Shoudai and S. Miyano, April, 1993.
  69. Complexity of computing Vapnik-Chervonenkis dimension,
    A. Shinohara, April, 1993 (Lecture Notes in Artificial Intelligence 744, 279-287, 1993).
  70. Inductive inference of Prolog programs with linear data dependency from positive data,
    H. Arimura, T. Shinohara, May, 1993 (To appear in Proc. 3rd Eur-Jap Seminar on Information Modeling and Knowledge Bases).
  71. Minimal multiple generalization for unions of pattern languages,
    H. Arimura, T. Shinohara and S. Otsuki, May, 1993.
  72. Finding minimal models by the semantic tableaux system,
    K. Hirata, May, 1993.
  73. Learning theory toward genome informatics,
    S. Miyano, July, 1993 (Lecture Notes in Artificial Intelligence 744, 19-36, 1993).
  74. Inductive inference of an approximate concept from positive data,
    Y. Mukouchi, September, 1993 (Revised: January, 1994).
  75. Polynomial Time Algorithm Solving the Refutation Tree Problem for Formal Graph Systems,
    T. Uchida, T. Shoudai and S. Miyano, September, 1993 (Bulletin of Informatics and Cybernetics, Vol. 26, 55--74, 1994).
  76. Partially isomorphic generalization and analogical reasoning,
    E. Hirowatari and S. Arikawa, October, 1993 (Proc. European Conference on Machine Learning (Lecture Notes in Artificial Intelligence 784), 363-366, 1994).
  77. A classification of abduction,
    K. Hirata, October, 1993 (to appear Machine Intelligence,14).
  78. Complexity of computing generalized VC-dimensions,
    A. Shinohara, October, 1993 (Proc. European Conference on Machine Learning (Lecture Notes in Artificial Intelligence 784), 415-418, 1994).
  79. Language learning by inverse resolution on elementary formal systems,
    C. Zeng and S. Arikawa, January, 1994.
  80. The recurrence of dynamic fuzzy systems,
    Y. Yoshida, February, 1994.
  81. Unions of a bounded number of tree pattern languages are hard to learn,
    H. Arimura, February, 1994.
  82. Inductive inference of recursive concepts,
    Y. Mukouchi, March, 1994 (Ph.D. Thesis).
  83. Formal graph systems and parallel graph algorithm design,
    T. Uchida, March, 1994 (Ph.D. Thesis).
  84. Introducing types into elementary formal systems,
    K. Kiwata and S. Arikawa, April, 1994.
  85. Rule-generating abduction for recursive prolog,
    K. Hirata, April,1994 (Proc. 5th Intern. Workshop on Analogical and Inductive Inference for Program Synthesis).
  86. Explanation-based reuse of prolog programs,
    Y. Koga, E. Hirowatari, and S. Arikawa, April, 1994 (Proc. 5th Intern. Workshop on Analogical and Inductive Inference for Program Synthesis) .
  87. Refutably probably approximately correct learning,
    S. Matsumoto and A. Shinohara, April, 1994 (Proc. 5th Intern. Workshop on Algorithmic Learning Theory ).
  88. Markov chains with a transition possibility measure and fuzzy dynamic programming,
    Y. Yoshida, May, 1994.
  89. The transitive closure of fuzzy relations with a contraction property,
    Y. Yoshida, May, 1994.
  90. A small final coalgebra theorem,
    Y. Kawahara and M. Mori, June, 1994.
  91. A reduction rule for Peirce's formula makes all the terms with the same type equal,
    S. Hirokawa, Y. Komori and I. Takeuti, September, 1994.
  92. Infiniteness of proof(\alpha) is polynomial-space complete,
    S. Hirokawa, September, 1994.
  93. A characterization of implicational axiom schema playing the role of Peirce's law in intuitionistic logic,
    S. Hirokawa, September, 1994.
  94. Graph inference from a walk for trees of bounded degree 3 is NP-complete,
    O. Maruyama and S. Miyano, September, 1994.
  95. A note on rule-finding abduction,
    K. Hirata, November, 1994.
  96. An aproximation algorithm for alphabet indexing problem,
    S. Shimozono, January, 1995.
  97. Relational set theory,
    Y. Kawahara, February, 1995.
  98. An algebraic formalization of fuzzy relations,
    Y. Kawahara and H. Furusawa, February, 1995.
  99. BONSAI garden: Parallel knowledge discovery system for amino acid sequences,
    T. Shoudai, M. Lappe, S. Miyano, A. Shinohara, T. Okazaki, S. Arikawa, T. Uchida, S. Shimozono, T. Shinohara and S. Kuhara, February, 1995.
  100. Superharmonic fuzzy sets on recurrent sets in dynamic fuzzy systems,
    Y. Yoshida, February,1995.
  101. Cyclic classes and an ergodic theorem in dynamic fuzzy systems,
    Y. Yoshida, February, 1995.
  102. An optimal stopping problem in dynamic fuzzy systems with fuzzy rewards,
    Y. Yoshida, February, 1995.
  103. A minmax theorem for zero-sum stopping games in dynamic fuzzy systems,
    Y. Yoshida, February, 1995.
  104. Duality in dynamic fuzzy systems,
    Y. Yoshida, February, 1995.
  105. Two variations of inductive inference of languages from positive data,
    T. Tabe and T. Zeugmann, March, 1995.
  106. Rule-based abduction for login programming,
    K. Hirata, March, 1995. (Ph.D.Thesis).
  107. Properties of elementary formal system as translation grammars,
    N. Sugimoto, April, 1995.
  108. Language learning with characteristic examples and membership queries,
    H. Sakamoto, April, 1995.
  109. Theory-generating abduction from finite good examples,
    K. Hirata, April, 1995.
  110. Co-learning of recursive languages from positive data,
    R. Freivalds and T. Zeugmann, April, 1995.
  111. Lange and Wiehagen's pattern language learning algorithm:an average-case analysis with respect to its total learning time,
    T. Zeugmann, April, 1995.
  112. Refutable inference of functions computed by loop programs,
    T. Miyahara, April, 1995.
  113. Learning of associative memory network by penalty methods,
    K. Niijima, April, 1995.
  114. Another quantum Turing machine,
    D. Ikeda and S. Arikawa, may, 1995.
  115. Extracting motifs from positive and negative sequence data,
    E. Tateishi, O. Maruyama and S. Miyano, June, 1995.
  116. Taking a walk in a graph,
    O. Maruyama, and S. Miyano, July, 1995.
  117. Modeling Incremental Learning from Positive Data,
    S. Lange, and T. Zeugmann, August, 1995.
  118. A greedy strategy for finding motifs from positive and negative examples,
    E. Tateishi and S. Miyano, August, 1995.
  119. Period Lengths of Cellular Automata cam - 90 with Memory,
    Y.Kawahara and Hyen Yeal Lee, October, 1995.
  120. Polynomial Time Learnability of Deterministic Right Linear Translations,
    N.Sugimoto and H.Ishizaka, October, 1995.
  121. Transition Diagrams of Finite Cellular Automata,
    Hyen Yeal Lee and Y.Kawahara, November, 1995.
  122. Learning by Erasing,
    S.Lange, R.Wiehagen and T.Zeugmann, February, 1996.
  123. Graph Inference from Walks,
    O.maruyama, December, 1995.