• 研究課題をさがす
  • 研究者をさがす
  • KAKENの使い方
  1. 前のページに戻る

山上 智幸  YAMAKAMI TOMOYUKI

ORCIDORCID連携する *注記
研究者番号 80230324
所属 (現在) 2025年度: 福井大学, 学術研究院工学系部門, 教授
所属 (過去の研究課題情報に基づく) *注記 2025年度: 福井大学, 学術研究院工学系部門, 教授
2016年度 – 2023年度: 福井大学, 学術研究院工学系部門, 教授
2012年度 – 2014年度: 福井大学, 工学(系)研究科(研究院), 教授
2009年度: 福井大学, 大学院・工学研究科, 教授
2007年度 – 2008年度: 会津大学, コンピュータ理工学部, 上級准教授
審査区分/研究分野
研究代表者
小区分60010:情報学基礎論関連 / 情報学基礎 / 情報学基礎理論
キーワード
研究代表者
メモリ領域 / オートマトン / 弱線形メモリ領域計算 / 線形メモリ領域仮説 / 線形領域仮説 / 多項式時間 / プッシュダウンオートマトン / 対数領域計算 / アルゴリズムの効率 / 計算量理論 … もっと見る / アドバイス / 量子計算 / 量子ソフトウェア / 量子帰納的関数 / 量子論理 / 接続経路探索問題 / NL制約充足問題 / パラメタ付き決定問題 / 量子アニーリング / 線形メモリ領域量仮説 / NL完全問題 / シンクロナイゼーション / 多項式時間アルゴリズム / 弱線形メモリ領域 / ファジー技術 / 量子コンピュータ / 機械学習 / データマイニング / 情報の論理的な深さ / 並列計算 / コルモゴロフ計算量 / 滝型論理回路 / 一様性有限オートマトン族 / 弱線型メモリ領域 / 線型領域仮説 / 多項式時間計算 / 非一様性有限オートマトン族 / 1進数表示 / スト―リッジオートマトン / 弱線形メモリ領域仮説 / 非一様オートマトン族 / 量子アディアバティック計算 / 対数メモリ領域 / メモリ領域仮説 / NL探索問題 / 探索アルゴリズム / メモリ領域量 / 線形計画法 / 論理式充足判定問題 / 有向グラフ経路探索問題 / パラメタ化 / 半線形領域計算量 / 巨大ベータ処理 / 決定性アルゴリズムの効率 / NL 探索問題 / NL 最適化問題 / 非決定性対数領域計算 / アルゴリズム / トポロジカルオートマトン / 計算モデル / 内部状態数 / 弱線形メモリ領域還元 / オンラインアルゴリズム / 使用メモリ領域量 / #P完全 / Holant問題 / 近似保存還元性 / 最適解近似アルゴリズム / 小型計算機端末 / 解法アルゴリズムの効率 / 時間・領域計算量 / リスト分割数え上げ問題 / 固定長領域計算量 / 対数領域計算可能性 / 解の数え上げ問題 / 制約充足問題の最適解探索 / プッシュダウン・オートマトン / 時間計算量 / リスト行列グラフ分割問題 / 2極値定理 / #P完全 / 数え上げ問題 / 最適化問題 / 制約充足問題 / 量子記憶 / 高速通信ネットーワーク / 安全性 / 量子アルゴリズム / 量子計算モデル / 量子対話証明 / 計算量 / 量子状態 / 量子証明 / 量子ハードコア関数 / 量子リスト復号 / 量子ゼロ知識証明 / 量子オートマトン / 量子暗号 隠す
  • 研究課題

    (5件)
  • 研究成果

    (90件)
  • 共同研究者

    (1人)
  •  量子帰納的関数と量子論理による量子計算の特徴付けと量子ソフトウェア開発への応用研究代表者

    • 研究代表者
      山上 智幸
    • 研究期間 (年度)
      2025 – 2027
    • 研究種目
      基盤研究(C)
    • 審査区分
      小区分60010:情報学基礎論関連
    • 研究機関
      福井大学
  •  小型デバイス上でのデータ処理アルゴリズムの使用メモリ領域の効率化研究代表者

    • 研究代表者
      山上 智幸
    • 研究期間 (年度)
      2019 – 2023
    • 研究種目
      基盤研究(C)
    • 審査区分
      小区分60010:情報学基礎論関連
    • 研究機関
      福井大学
  •  NL探索問題の探索アルゴリズム分析によるメモリ領域量の解明研究代表者

    • 研究代表者
      山上 智幸
    • 研究期間 (年度)
      2016 – 2018
    • 研究種目
      基盤研究(C)
    • 研究分野
      情報学基礎理論
    • 研究機関
      福井大学
  •  制約充足問題の最適解近似アルゴリズムを高速化する制約条件の簡単な識別方法研究代表者

    • 研究代表者
      山上 智幸
    • 研究期間 (年度)
      2012 – 2014
    • 研究種目
      基盤研究(C)
    • 研究分野
      情報学基礎
    • 研究機関
      福井大学
  •  量子対話知識証明の分析と量子暗号への応用研究代表者

    • 研究代表者
      山上 智幸
    • 研究期間 (年度)
      2007 – 2009
    • 研究種目
      基盤研究(C)
    • 研究分野
      情報学基礎
    • 研究機関
      福井大学
      会津大学

すべて 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2010 2009 2008 2007

すべて 雑誌論文 学会発表

  • [雑誌論文] Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata2023

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      International Journal of Computer Mathematics: Computer Systems Theory

      巻: 8 号: 1 ページ: 1-31

    • DOI

      10.1080/23799927.2023.2166872

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] When input integers are given in the unary numeral representation2023

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 24th Italian Conference on Theoretical Computer Science (ICTCS 2023), CEUR Workshop Proceedings (CEUR-WS.org)

      巻: 3587 ページ: 268-282

    • 査読あり / オープンアクセス
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] The 2CNF Boolean formula satisfiability problem and the linear space hypothesis2023

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Journal of Computer and System Sciences

      巻: 136 ページ: 88-112

    • DOI

      10.1016/j.jcss.2023.03.001

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Synchronizing deterministic push-down automata can be really hard2023

    • 著者名/発表者名
      Henning Fernau, Petra Wolf, Tomoyuki Yamakami
    • 雑誌名

      Information and Computation

      巻: 295 ページ: 105089-105089

    • DOI

      10.1016/j.ic.2023.105089

    • 査読あり / 国際共著/国際学会である
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Power of counting by nonuniform families of polynomial-size finite automata2023

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceeding of the 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), Lecture Notes in Computer Science

      巻: 14292 ページ: 421-435

    • DOI

      10.1007/978-3-031-43587-4_30

    • ISBN
      9783031435867, 9783031435874
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits (Extended Abstract)2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 28th International Conference on Computing and Combinatorics, Lecture Notes in Computer Science

      巻: 13595 ページ: 61-69

    • DOI

      10.1007/978-3-031-22105-7_6

    • ISBN
      9783031221040, 9783031221057
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Information and Computation

      巻: 286 ページ: 104783-104783

    • DOI

      10.1016/j.ic.2021.104783

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report)2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 25th International Computer Symposium on New Trends in Computer Technologies and Applications, Communications in Computer and Information Science

      巻: 1723 ページ: 180-191

    • DOI

      10.1007/978-981-19-9582-8_16

    • ISBN
      9789811995811, 9789811995828
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the Future Technologies Conference, Lecture Notes in Networks and Systems

      巻: 559 ページ: 776-795

    • DOI

      10.1007/978-3-031-18461-1_51

    • ISBN
      9783031184604, 9783031184611
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Formal Grammars for Turn-Bounded Deterministic Context-Free Languages2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 19th International Colloquium on Theoretical Aspects of Computing, Lecture Notes in Computer Science

      巻: 13572 ページ: 425-441

    • DOI

      10.1007/978-3-031-17715-6_27

    • ISBN
      9783031177149, 9783031177156
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 16th International Conference on Reachability Problems, Lecture Notes in Computer Science

      巻: 13608 ページ: 77-92

    • DOI

      10.1007/978-3-031-19135-0_6

    • ISBN
      9783031191343, 9783031191350
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 28th International Workshop on Logic, Language, Information, and Computation, Lecture Notes in Computer Science

      巻: 13468 ページ: 88-104

    • DOI

      10.1007/978-3-031-15298-6_6

    • ISBN
      9783031152979, 9783031152986
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata2022

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 26th International Conference on Developments in Language Theory, Lecture Notes in Computer Science

      巻: 13257 ページ: 312-324

    • DOI

      10.1007/978-3-031-05578-2_25

    • ISBN
      9783031055775, 9783031055782
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report)2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      電子情報通信学会, 情報理論研究会, 信学技報

      巻: IT2020-117 ページ: 31-36

    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Nondeterministically selecting positive instances of context-free languages2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 22nd Italian Conference on Theoretical Computer Science, CEUR Workshop Proceedings

      巻: 3072 ページ: 249-265

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-k storage automata2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 27th International Computing and Combinatorics Conference, Lecture Notes in Computer Science

      巻: 13025 ページ: 164-175

    • DOI

      10.1007/978-3-030-89543-3_14

    • ISBN
      9783030895426, 9783030895433
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 19th International Conference on Unconventional Computation and Natural Computation, Lecture Notes in Computer Science

      巻: 12984 ページ: 177-193

    • DOI

      10.1007/978-3-030-87993-8_12

    • ISBN
      9783030879921, 9783030879938
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Fuzzy Kolmogorov complexity based on fuzzy decompression algorithms and its application to fuzzy data mining (preliminary report)2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 17th International Conference on Advanced Data Mining and Applications, Lecture Notes in Computer Science

      巻: 13087 ページ: 421-436

    • DOI

      10.1007/978-3-030-95405-5_30

    • ISBN
      9783030954048, 9783030954055
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Synchronizing words for real-time deterministic pushdown automata (extended abstract)2021

    • 著者名/発表者名
      Tomoyuki Yamakami and Eitatsu Mikami
    • 雑誌名

      Proceedings of the Seventh International Conference on Mathematics and Computing, Advances in Intelligent Systems and Computing

      巻: 1412 ページ: 551-562

    • DOI

      10.1007/978-981-16-6890-6_41

    • ISBN
      9789811668890, 9789811668906
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] One-Way Topological Automata and the Tantalizing Effects of Their Topological Features2020

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Journal of Automata, Languages and Combinatorics

      巻: 25 ページ: 235-273

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] A Schematic Definition of quantum Polynomial Time Computability2020

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      The Journal of Symbolic Logic

      巻: 85 号: 4 ページ: 1546-1587

    • DOI

      10.1017/jsl.2020.45

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Intersection and union hierarchies of deterministic context-free languages and pumping lemmas2020

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 14th International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science

      巻: 12038 ページ: 341-353

    • DOI

      10.1007/978-3-030-40608-0_24

    • ISBN
      9783030406073, 9783030406080
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Synchronizing Deterministic Push-Down Automata Can Be Really Hard2020

    • 著者名/発表者名
      Henning Fernau, Petra Wolf, Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2020

      巻: 170

    • 査読あり / 国際共著/国際学会である
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Theoretical Computer Science

      巻: 798 ページ: 2-22

    • DOI

      10.1016/j.tcs.2019.09.006

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Relativizations of nonuniform quantum finite automata families2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 8th International Conference on Unconventional Computation and Natural Computation, Lecture Notes in Computer Science

      巻: 11493 ページ: 257-271

    • DOI

      10.1007/978-3-030-19311-9_20

    • ISBN
      9783030193102, 9783030193119
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 13th International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science, Springer-Verlag

      巻: 11417 ページ: 134-145

    • DOI

      10.1007/978-3-030-13435-8_10

    • ISBN
      9783030134341, 9783030134358
    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] Behavioral strengths and weaknesses of various models of limited automata2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science, Springer-Verlag

      巻: 11376 ページ: 519-530

    • DOI

      10.1007/978-3-030-10801-4_40

    • ISBN
      9783030108007, 9783030108014
    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] upportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science

      巻: 11436 ページ: 659-673

    • DOI

      10.1007/978-3-030-14812-6_41

    • ISBN
      9783030148119, 9783030148126
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] How does adiabatic quantum computation fit into quantum automata theory?2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 21st IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science

      巻: 11612 ページ: 285-297

    • DOI

      10.1007/978-3-030-23247-4_22

    • ISBN
      9783030232467, 9783030232474
    • 査読あり
    • データソース
      KAKENHI-PROJECT-19K11820
  • [雑誌論文] One-way topological automata and the tantalizing effects of their topological features2018

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 10th Workshop on Non-Classical Models of Automata and Applications, Osterreichische Computer Gesellschaft, the Austrian Computer Society

      巻: 2018 ページ: 197-214

    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis2018

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science, Springer-Verlag

      巻: 10952 ページ: 237-249

    • DOI

      10.1007/978-3-319-94631-3_20

    • ISBN
      9783319946306, 9783319946313
    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)2017

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 21st International Conference on Developments in Language Theory (DLT 2017), Lecture Notes in Computer Science, Springer-Verlag

      巻: 10396 ページ: 353-364

    • DOI

      10.1007/978-3-319-62809-7_28

    • ISBN
      9783319628080, 9783319628097
    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] The 2CNF Boolean formula satisfiability problem and the linear space hypothesis2017

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Leibniz International Proceedings in Informatics (LIPIcs)

      巻: 83

    • DOI

      10.4230/LIPIcs.MFCS.2017.6

    • 査読あり / オープンアクセス
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)2017

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 11th International Workshop on Reachability Problems (RP 2017), Lecture Notes in Computer Science, Springer-Verlag

      巻: 10506 ページ: 176-191

    • DOI

      10.1007/978-3-319-67089-8_13

    • ISBN
      9783319670881, 9783319670898
    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] A recursive definition of quantum polynomial time computability (extended abstract)2017

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 9th Workshop on Non-Classical Models of Automata and Applications (NCMA 2017), Osterreichische Computer Gesellschaft 2017, the Austrian Computer Society

      巻: 2017 ページ: 243-258

    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] Quantum list decoding of classical block codes of polynomially small rate from quantumly corrupted codewords2016

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Baltic Journal of Modern Computing

      巻: 4(4) ページ: 753-788

    • 査読あり / オープンアクセス
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] Pseudorandom generators against advised context-free languages2016

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Theoretical Computer Science

      巻: 613 ページ: 1-27

    • DOI

      10.1016/j.tcs.2015.10.026

    • 査読あり
    • データソース
      KAKENHI-PROJECT-16K00013
  • [雑誌論文] Interactive proofs with quantum finite automata2015

    • 著者名/発表者名
      H. Nishimura and T. Yamakami
    • 雑誌名

      Theoretical Computer Science

      巻: 568 ページ: 1-18

    • DOI

      10.1016/j.tcs.2014.11.030

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Counting list matrix partitions of graphs2015

    • 著者名/発表者名
      A. Goebel, L. A. Goldberg, C. McQuillan, D. Richerby, and T. Yamakami
    • 雑誌名

      SIAM Journal on Computing

      巻: 00 ページ: 00-00

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Counting list matrix partitions of graphs2014

    • 著者名/発表者名
      Andreas Goebel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, and Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the IEEE Conference on Computational Complexity

      巻: in press

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems2014

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Theory of Computing Systems

      巻: in press 号: 1 ページ: 170-201

    • DOI

      10.1007/s00224-013-9518-4

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] One-way reversible and quantum finite automata with advice2014

    • 著者名/発表者名
      T. Yamakami
    • 雑誌名

      Information and Computation

      巻: 239 号: 11 ページ: 611-619

    • DOI

      10.1016/j.ipl.2014.05.012

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms2014

    • 著者名/発表者名
      T. Yamakami
    • 雑誌名

      Proceedings of the Joint 7th International Conference on Soft Computing and Intelligent Systems and 15th International Symposium on Advanced Intelligent Systems

      巻: 2014 ページ: 29-35

    • DOI

      10.1109/scis-isis.2014.7044695

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata (extended abstract)2014

    • 著者名/発表者名
      T. Yamakami
    • 雑誌名

      Proceedings of the 15th Italian Conference on Theoretical Computer Science, CEUR Workshop Proceedings

      巻: 1231

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)2014

    • 著者名/発表者名
      T. Yamakami
    • 雑誌名

      Proceedings of the 8th IFIP International Conference on Theoretical Computer Science, Lecture Notes in Computer Science

      巻: 8705 ページ: 136-150

    • DOI

      10.1007/978-3-662-44602-7_12

    • ISBN
      9783642387081, 9783642387098
    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages2014

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science

      巻: 8327 ページ: 514-525

    • DOI

      10.1007/978-3-319-04298-5_45

    • ISBN
      9783319042978, 9783319042985
    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Quantum and Reversible Verification of Proofs Using Constant Memory Space2014

    • 著者名/発表者名
      Marcos Villagra and Tomoyuki Yamakami
    • 雑誌名

      Lecture Notes in Computer Science

      巻: 8890 ページ: 144-156

    • DOI

      10.1007/978-3-319-13749-0_13

    • ISBN
      9783319137483, 9783319137490
    • 査読あり
    • データソース
      KAKENHI-PROJECT-13J06353, KAKENHI-PROJECT-24500011
  • [雑誌論文] Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems2013

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 7th Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science

      巻: 8287 ページ: 318-329

    • DOI

      10.1007/978-3-319-03780-6_28

    • ISBN
      9783319037790, 9783319037806
    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] The dissecting power of regular languages2013

    • 著者名/発表者名
      Tomoyuki Yamakami and Yuichi Kato
    • 雑誌名

      Information Processing Letters

      巻: 113 号: 4 ページ: 116-122

    • DOI

      10.1016/j.ipl.2012.12.006

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Theoretical Computer Science

      巻: 447 ページ: 120-135

    • DOI

      10.1016/j.tcs.2012.03.036

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Computational indistinguishability between quantum states and its cryptographic application2012

    • 著者名/発表者名
      Akinori Kawachi. Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami
    • 雑誌名

      Journal of Cryptology

      巻: 25 号: 3 ページ: 528-555

    • DOI

      10.1007/s00145-011-9103-4

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Theoretical Computer Science

      巻: 461 ページ: 86-105

    • DOI

      10.1016/j.tcs.2011.11.037

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Constant unary constraints and symmetric real-weighted counting CSPs2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 23rd International Symposium on Algorithms and Computation, Lecture Notes in Computer Science

      巻: 7676 ページ: 237-246

    • DOI

      10.1007/978-3-642-35261-4_27

    • ISBN
      9783642352607, 9783642352614
    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Approximate counting for complex-weighted Boolean constraint satisfaction problems2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Information and Computation

      巻: 219 ページ: 17-38

    • DOI

      10.1016/j.ic.2012.08.002

    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] One-way reversible and quantum finite automata with advice2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 雑誌名

      Proceedings of the 6th International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science

      巻: 7183 ページ: 526-537

    • DOI

      10.1007/978-3-642-28332-1_45

    • ISBN
      9783642283314, 9783642283321
    • 査読あり
    • データソース
      KAKENHI-PROJECT-24500011
  • [雑誌論文] Quantum hardcore functions by complexity-theoretical list decoding2010

    • 著者名/発表者名
      A.Kawachi, T.Yamakami
    • 雑誌名

      SIAM Journal on Computing 39

      ページ: 2941-2969

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19500015
  • [雑誌論文] Theory of one tape linear time Turing machines2010

    • 著者名/発表者名
      K.Tadaki, T.Yamakami, J.C.H.Lin
    • 雑誌名

      Theoretical Computer Science 411

      ページ: 22-43

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19500015
  • [雑誌論文] An application of quantum finite automata to interactive proof systems2009

    • 著者名/発表者名
      Harumichi Nishimura, Tomoyuki Yamakami
    • 雑誌名

      Journal of Computer and System Sciences 75(4)

      ページ: 255-269

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19500015
  • [雑誌論文] The roles of advice to one-tape linear-time Turing machines and finite automata. Accepted for publication at International Journal of Foundations of Computer Science, 20102009

    • 著者名/発表者名
      T. Yamakami
    • 雑誌名

      A conference version appeared in ISAAC 2009, Lecture Notes in Computer Science Vol. 5878

      ページ: 933-942

    • データソース
      KAKENHI-PROJECT-19500015
  • [雑誌論文] Quantum Merlin-Arthur proof systems : are multiple Merlins more helpful to Arthur?2009

    • 著者名/発表者名
      H.Kobayashi, K.Matsumoto, T.Yamakami
    • 雑誌名

      Chicago Journal of Theoretical Computer Science 2009

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19500015
  • [雑誌論文] The efficiency of quantum identity testing of multiple states2008

    • 著者名/発表者名
      Masaru Kada, Harumichi Nishimura, Tomoyuki Yamakami
    • 雑誌名

      Journal of Physics A : Mathematical and Theoretical 41(3)

      ページ: 395309-395309

    • 査読あり
    • データソース
      KAKENHI-PROJECT-19500015
  • [学会発表] When Input Integers are Given in the Unary Numeral Representation (Preliminary Report)2023

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会 コンピュテーション研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] When input integers are given in the unary numeral representation -- (preliminary report) --2023

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会 コンピュテーション研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report)2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会  情報理論研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Nondeterministically selecting positive instances of context-free languages2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The 22nd Italian Conference on Theoretical Computer Science
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-k storage automata2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The 27th International Computing and Combinatorics Conference
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Synchronizing words for real-time deterministic pushdown automata2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The 7th International Conference on Mathematics and Computing
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report)2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会 情報理論研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Synchronizing Words for Real-Time Deterministic Pushdown Automata2021

    • 著者名/発表者名
      Tomoyuki Yamakami, Eitatsu Mikami
    • 学会等名
      The 7th International Conference on Mathematics and Computing
    • 国際共著/国際学会である
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The 19th International Conference on Unconventional Computation and Natural Computation
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Fuzzy Kolmogorov complexity based on fuzzy decompression algorithms and its application to fuzzy data mining2021

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The 17th International Conference on Advanced Data Mining and Applications
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] シンクロナイジングプッシュダウンオートマトンとリセットワード2020

    • 著者名/発表者名
      三神栄達・山上智幸
    • 学会等名
      電子情報通信学会コンピュテーション研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] What Restrictions Naturally Allow Well-Known NP-Complete Problems to Yield NL-Completeness and the Linear Space Hypothesis?2020

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会 コンピュテーション研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Type-2 Computability, Generic Oracles, and the Linear Space Hypothesis2019

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      Higher-order Complexity Theory and its Applications
    • 招待講演 / 国際共著/国際学会である
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] 書き換え制限付き決定性オートマトンと繰り返し補題2019

    • 著者名/発表者名
      吉田光星・山上智幸
    • 学会等名
      電子情報通信学会コンピュテーション研究会
    • データソース
      KAKENHI-PROJECT-19K11820
  • [学会発表] Non-uniform state complexity of quantum finite automata and quantum polynomial-time logarithmic-space computation with quantum advice -- (preliminary report) --2018

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会 量子情報技術研究会(QIT)
    • データソース
      KAKENHI-PROJECT-16K00013
  • [学会発表] State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis2018

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      情報処理学会 アルゴリズム研究会(SIGAL)
    • データソース
      KAKENHI-PROJECT-16K00013
  • [学会発表] The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms (preliminary report)2014

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会コンピュテーション研究会
    • 発表場所
      豊橋技科大
    • 年月日
      2014-09-02
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] The state complexity of two-way quantum finite automata (preliminary report)2014

    • 著者名/発表者名
      Marcos Villagra and Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会コンピュテーション研究会
    • 発表場所
      中央大学
    • 年月日
      2014-10-08
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] Non-Interactive Proof Verification Procedures of Reversible and Quantum Finite Automata2014

    • 著者名/発表者名
      Marcos Villagra and Tomoyuki Yamakami
    • 学会等名
      情報処理学会、アルゴリズム研究会
    • 発表場所
      中央大学後楽園キャンパス
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] Constant-Space Zero-Knowledge Proofs Systems with One-Way Quantum Verifiers (Preliminary Report)2013

    • 著者名/発表者名
      Marcos Villagra and Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会、コンピュテーション研究会
    • 発表場所
      名古屋工業大学
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] Approximation classification of complex-weighted counting CSPs2013

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      Dagstuhl Seminar 13031- Computational Counting, Schloss Dagstuhl, Leibniz-Zentrum für Informatik
    • 発表場所
      Schloss Dagstuhl, Germany
    • 招待講演
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages (Preliminary Version)2013

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      電子情報通信学会、コンピュテーション研究会
    • 発表場所
      鳥取環境大学
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] Nondeterministic pushdown automata with write-only output tapes and definable function classes2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      情報処理学会 第142回アルゴリズム研究会
    • 発表場所
      岩手大学
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] The dissecting power of regular languages2012

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The 15th Japan-Korea Joint Workshop on Algorithms and Computation
    • 発表場所
      国立情報学研究所、東京
    • データソース
      KAKENHI-PROJECT-24500011
  • [学会発表] Quantum finite automata with advice2009

    • 著者名/発表者名
      T. Yamakami
    • 学会等名
      情報処理学会、第127回アルゴリズム研究会
    • 発表場所
      名古屋大学
    • データソース
      KAKENHI-PROJECT-19500015
  • [学会発表] The role of advice to linear-time Turing machines and finite automata2009

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      Proc.20th International Symposium on Algorithms and Computing(ISAAC 2009)
    • 発表場所
      Honolulu, Hawaii, USA
    • 年月日
      2009-12-18
    • データソース
      KAKENHI-PROJECT-19500015
  • [学会発表] Quantum finite automata with advice2009

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      情報処理学会 第127回アルゴリズム研究会
    • 発表場所
      名古屋大学
    • 年月日
      2009-11-27
    • データソース
      KAKENHI-PROJECT-19500015
  • [学会発表] Multiple Quantum Zero-Knowledge Proofs with Constant Space Verifiers2007

    • 著者名/発表者名
      Tomoyuki Yamakami
    • 学会等名
      The Fourth Central European Quantum Information Processing Workshop (CEQIP 2007)
    • 発表場所
      Valtice, Czech Republic
    • 年月日
      2007-06-27
    • データソース
      KAKENHI-PROJECT-19500015
  • [学会発表] Quantum list decoding from quantumly corrupted codewords for classical block codes of polynomially small rate2007

    • 著者名/発表者名
      T. Yamakami
    • 学会等名
      Proceedings of the Thirteenth Computing : The Australasian Theory Symposium (CATS 2007)
    • 発表場所
      Ballarat, Australia
    • データソース
      KAKENHI-PROJECT-19500015
  • 1.  VILLAGRA Marcos
    共同の研究課題数: 0件
    共同の研究成果数: 2件

URL: 

この研究者とORCID iDの連携を行いますか?
※ この処理は、研究者本人だけが実行できます。

Are you sure that you want to link your ORCID iD to your KAKEN Researcher profile?
* This action can be performed only by the researcher himself/herself who is listed on the KAKEN Researcher’s page. Are you sure that this KAKEN Researcher’s page is your page?

サービス概要 検索マニュアル よくある質問 お知らせ 利用規程 科研費による研究の帰属

Powered by NII kakenhi