YAMAKAMI TOMOYUKI 山上智幸

… Alternative Names

山上智幸ヤマカミトモユキ

YAMAKAMI Tomoyuki 山上智幸

Less

Researcher Number	80230324
Affiliation (Current)	2026: 福井大学, 学術研究院工学系部門, 教授
Affiliation (based on the past Project Information) *help	2025: 福井大学, 学術研究院工学系部門, 教授 2016 – 2023: 福井大学, 学術研究院工学系部門, 教授 2012 – 2014: 福井大学, 工学(系)研究科(研究院), 教授 2009: The University of Aizu, 大学院・工学研究科, 教授 2007 – 2008: The University of Aizu, コンピュータ理工学部, 上級准教授
Review Section/Research Field	Principal Investigator Basic Section 60010:Theory of informatics-related / Fundamental theory of informatics / Theory of informatics
Keywords	Principal Investigator メモリ領域 / オートマトン / 弱線形メモリ領域計算 / 線形メモリ領域仮説 / 線形領域仮説 / 多項式時間 / プッシュダウンオートマトン / 対数領域計算 / アルゴリズムの効率 / 計算量理論 … More / アドバイス / 量子計算 / 量子ソフトウェア / 量子帰納的関数 / 量子論理 / 接続経路探索問題 / NL制約充足問題 / パラメタ付き決定問題 / 量子アニーリング / 線形メモリ領域量仮説 / NL完全問題 / シンクロナイゼーション / 多項式時間アルゴリズム / 弱線形メモリ領域 / ファジー技術 / 量子コンピュータ / 機械学習 / データマイニング / 情報の論理的な深さ / 並列計算 / コルモゴロフ計算量 / 滝型論理回路 / 一様性有限オートマトン族 / 弱線型メモリ領域 / 線型領域仮説 / 多項式時間計算 / 非一様性有限オートマトン族 / １進数表示 / スト―リッジオートマトン / 弱線形メモリ領域仮説 / 非一様オートマトン族 / 量子アディアバティック計算 / 対数メモリ領域 / メモリ領域仮説 / NL探索問題 / 探索アルゴリズム / メモリ領域量 / 線形計画法 / 論理式充足判定問題 / 有向グラフ経路探索問題 / パラメタ化 / 半線形領域計算量 / 巨大ベータ処理 / 決定性アルゴリズムの効率 / NL 探索問題 / NL 最適化問題 / 非決定性対数領域計算 / アルゴリズム / トポロジカルオートマトン / 計算モデル / 内部状態数 / 弱線形メモリ領域還元 / オンラインアルゴリズム / 使用メモリ領域量 / #P完全 / Holant問題 / 近似保存還元性 / 最適解近似アルゴリズム / 小型計算機端末 / 解法アルゴリズムの効率 / 時間・領域計算量 / リスト分割数え上げ問題 / 固定長領域計算量 / 対数領域計算可能性 / 解の数え上げ問題 / 制約充足問題の最適解探索 / プッシュダウン・オートマトン / 時間計算量 / リスト行列グラフ分割問題 / ２極値定理 / ＃P完全 / 数え上げ問題 / 最適化問題 / 制約充足問題 / 量子記憶 / 高速通信ネットーワーク / 安全性 / 量子アルゴリズム / 量子計算モデル / 量子対話証明 / 計算量 / 量子状態 / 量子証明 / 量子ハードコア関数 / 量子リスト復号 / 量子ゼロ知識証明 / 量子オートマトン / 量子暗号 Less

Characterization of quantum computing using quantum recursive functions and quantum logics and its application to quantum software developmentPrincipal Investigator
- Principal Investigator
  
  山上智幸
- Project Period (FY)
  2025 – 2027
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Review Section
  
  Basic Section 60010:Theory of informatics-related
- Research Institution
  University of Fukui
Efficient use of memory space by data processing algorithms on compact-size devicesPrincipal Investigator
- Principal Investigator
  
  Yamakami Tomoyuki
- Project Period (FY)
  2019 – 2023
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Review Section
  
  Basic Section 60010:Theory of informatics-related
- Research Institution
  University of Fukui
An Analysis of Memory Space Usage by Algorithms Solving NL Search ProblemsPrincipal Investigator
- Principal Investigator
  
  YAMAKAMI TOMOYUKI
- Project Period (FY)
  2016 – 2018
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Theory of informatics
- Research Institution
  University of Fukui
How to select constraints that help algorithms approximately solve constraint satisfaction problemsPrincipal Investigator
- Principal Investigator
  
  YAMAKAMI TOMOYUKI
- Project Period (FY)
  2012 – 2014
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  University of Fukui
An Analysis of Quantum Interactive Proofs and Their Application to Quantum CryptographyPrincipal Investigator
- Principal Investigator
  
  YAMAKAMI Tomoyuki
- Project Period (FY)
  2007 – 2009
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  University of Fukui
  The University of Aizu

[Journal Article] Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata2023
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  International Journal of Computer Mathematics: Computer Systems Theory
  
  Volume: 8 Issue: 1 Pages: 1-31
- DOI
  10.1080/23799927.2023.2166872
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] When input integers are given in the unary numeral representation2023
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 24th Italian Conference on Theoretical Computer Science (ICTCS 2023), CEUR Workshop Proceedings (CEUR-WS.org)
  
  Volume: 3587 Pages: 268-282
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] The 2CNF Boolean formula satisfiability problem and the linear space hypothesis2023
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Journal of Computer and System Sciences
  
  Volume: 136 Pages: 88-112
- DOI
  10.1016/j.jcss.2023.03.001
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Synchronizing deterministic push-down automata can be really hard2023
- Author(s)
  Henning Fernau, Petra Wolf, Tomoyuki Yamakami
- Journal Title
  
  Information and Computation
  
  Volume: 295 Pages: 105089-105089
- DOI
  10.1016/j.ic.2023.105089
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Power of counting by nonuniform families of polynomial-size finite automata2023
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceeding of the 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), Lecture Notes in Computer Science
  
  Volume: 14292 Pages: 421-435
- DOI
  10.1007/978-3-031-43587-4_30
- ISBN
  9783031435867, 9783031435874
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits (Extended Abstract)2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 28th International Conference on Computing and Combinatorics, Lecture Notes in Computer Science
  
  Volume: 13595 Pages: 61-69
- DOI
  10.1007/978-3-031-22105-7_6
- ISBN
  9783031221040, 9783031221057
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Information and Computation
  
  Volume: 286 Pages: 104783-104783
- DOI
  10.1016/j.ic.2021.104783
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report)2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 25th International Computer Symposium on New Trends in Computer Technologies and Applications, Communications in Computer and Information Science
  
  Volume: 1723 Pages: 180-191
- DOI
  10.1007/978-981-19-9582-8_16
- ISBN
  9789811995811, 9789811995828
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the Future Technologies Conference, Lecture Notes in Networks and Systems
  
  Volume: 559 Pages: 776-795
- DOI
  10.1007/978-3-031-18461-1_51
- ISBN
  9783031184604, 9783031184611
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Formal Grammars for Turn-Bounded Deterministic Context-Free Languages2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 19th International Colloquium on Theoretical Aspects of Computing, Lecture Notes in Computer Science
  
  Volume: 13572 Pages: 425-441
- DOI
  10.1007/978-3-031-17715-6_27
- ISBN
  9783031177149, 9783031177156
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 16th International Conference on Reachability Problems, Lecture Notes in Computer Science
  
  Volume: 13608 Pages: 77-92
- DOI
  10.1007/978-3-031-19135-0_6
- ISBN
  9783031191343, 9783031191350
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 28th International Workshop on Logic, Language, Information, and Computation, Lecture Notes in Computer Science
  
  Volume: 13468 Pages: 88-104
- DOI
  10.1007/978-3-031-15298-6_6
- ISBN
  9783031152979, 9783031152986
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata2022
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 26th International Conference on Developments in Language Theory, Lecture Notes in Computer Science
  
  Volume: 13257 Pages: 312-324
- DOI
  10.1007/978-3-031-05578-2_25
- ISBN
  9783031055775, 9783031055782
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report)2021
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  電子情報通信学会, 情報理論研究会, 信学技報
  
  Volume: IT2020-117 Pages: 31-36
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Nondeterministically selecting positive instances of context-free languages2021
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 22nd Italian Conference on Theoretical Computer Science, CEUR Workshop Proceedings
  
  Volume: 3072 Pages: 249-265
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-k storage automata2021
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 27th International Computing and Combinatorics Conference, Lecture Notes in Computer Science
  
  Volume: 13025 Pages: 164-175
- DOI
  10.1007/978-3-030-89543-3_14
- ISBN
  9783030895426, 9783030895433
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)2021
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 19th International Conference on Unconventional Computation and Natural Computation, Lecture Notes in Computer Science
  
  Volume: 12984 Pages: 177-193
- DOI
  10.1007/978-3-030-87993-8_12
- ISBN
  9783030879921, 9783030879938
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Fuzzy Kolmogorov complexity based on fuzzy decompression algorithms and its application to fuzzy data mining (preliminary report)2021
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 17th International Conference on Advanced Data Mining and Applications, Lecture Notes in Computer Science
  
  Volume: 13087 Pages: 421-436
- DOI
  10.1007/978-3-030-95405-5_30
- ISBN
  9783030954048, 9783030954055
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Synchronizing words for real-time deterministic pushdown automata (extended abstract)2021
- Author(s)
  Tomoyuki Yamakami and Eitatsu Mikami
- Journal Title
  
  Proceedings of the Seventh International Conference on Mathematics and Computing, Advances in Intelligent Systems and Computing
  
  Volume: 1412 Pages: 551-562
- DOI
  10.1007/978-981-16-6890-6_41
- ISBN
  9789811668890, 9789811668906
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] One-Way Topological Automata and the Tantalizing Effects of Their Topological Features2020
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Journal of Automata, Languages and Combinatorics
  
  Volume: 25 Pages: 235-273
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] A Schematic Definition of quantum Polynomial Time Computability2020
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  The Journal of Symbolic Logic
  
  Volume: 85 Issue: 4 Pages: 1546-1587
- DOI
  10.1017/jsl.2020.45
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Intersection and union hierarchies of deterministic context-free languages and pumping lemmas2020
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 14th International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science
  
  Volume: 12038 Pages: 341-353
- DOI
  10.1007/978-3-030-40608-0_24
- ISBN
  9783030406073, 9783030406080
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Synchronizing Deterministic Push-Down Automata Can Be Really Hard2020
- Author(s)
  Henning Fernau, Petra Wolf, Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2020
  
  Volume: 170
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis2019
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 798 Pages: 2-22
- DOI
  10.1016/j.tcs.2019.09.006
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Relativizations of nonuniform quantum finite automata families2019
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 8th International Conference on Unconventional Computation and Natural Computation, Lecture Notes in Computer Science
  
  Volume: 11493 Pages: 257-271
- DOI
  10.1007/978-3-030-19311-9_20
- ISBN
  9783030193102, 9783030193119
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice2019
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 13th International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science, Springer-Verlag
  
  Volume: 11417 Pages: 134-145
- DOI
  10.1007/978-3-030-13435-8_10
- ISBN
  9783030134341, 9783030134358
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] Behavioral strengths and weaknesses of various models of limited automata2019
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science, Springer-Verlag
  
  Volume: 11376 Pages: 519-530
- DOI
  10.1007/978-3-030-10801-4_40
- ISBN
  9783030108007, 9783030108014
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] upportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P2019
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science
  
  Volume: 11436 Pages: 659-673
- DOI
  10.1007/978-3-030-14812-6_41
- ISBN
  9783030148119, 9783030148126
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] How does adiabatic quantum computation fit into quantum automata theory?2019
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 21st IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science
  
  Volume: 11612 Pages: 285-297
- DOI
  10.1007/978-3-030-23247-4_22
- ISBN
  9783030232467, 9783030232474
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19K11820
[Journal Article] One-way topological automata and the tantalizing effects of their topological features2018
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 10th Workshop on Non-Classical Models of Automata and Applications, Osterreichische Computer Gesellschaft, the Austrian Computer Society
  
  Volume: 2018 Pages: 197-214
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis2018
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science, Springer-Verlag
  
  Volume: 10952 Pages: 237-249
- DOI
  10.1007/978-3-319-94631-3_20
- ISBN
  9783319946306, 9783319946313
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)2017
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 21st International Conference on Developments in Language Theory (DLT 2017), Lecture Notes in Computer Science, Springer-Verlag
  
  Volume: 10396 Pages: 353-364
- DOI
  10.1007/978-3-319-62809-7_28
- ISBN
  9783319628080, 9783319628097
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] The 2CNF Boolean formula satisfiability problem and the linear space hypothesis2017
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Leibniz International Proceedings in Informatics (LIPIcs)
  
  Volume: 83
- DOI
  10.4230/LIPIcs.MFCS.2017.6
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)2017
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 11th International Workshop on Reachability Problems (RP 2017), Lecture Notes in Computer Science, Springer-Verlag
  
  Volume: 10506 Pages: 176-191
- DOI
  10.1007/978-3-319-67089-8_13
- ISBN
  9783319670881, 9783319670898
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] A recursive definition of quantum polynomial time computability (extended abstract)2017
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 9th Workshop on Non-Classical Models of Automata and Applications (NCMA 2017), Osterreichische Computer Gesellschaft 2017, the Austrian Computer Society
  
  Volume: 2017 Pages: 243-258
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] Quantum list decoding of classical block codes of polynomially small rate from quantumly corrupted codewords2016
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Baltic Journal of Modern Computing
  
  Volume: 4(4) Pages: 753-788
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] Pseudorandom generators against advised context-free languages2016
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 613 Pages: 1-27
- DOI
  10.1016/j.tcs.2015.10.026
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16K00013
[Journal Article] Interactive proofs with quantum finite automata2015
- Author(s)
  H. Nishimura and T. Yamakami
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 568 Pages: 1-18
- DOI
  10.1016/j.tcs.2014.11.030
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Counting list matrix partitions of graphs2015
- Author(s)
  A. Goebel, L. A. Goldberg, C. McQuillan, D. Richerby, and T. Yamakami
- Journal Title
  
  SIAM Journal on Computing
  
  Volume: 00 Pages: 00-00
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Counting list matrix partitions of graphs2014
- Author(s)
  Andreas Goebel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, and Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the IEEE Conference on Computational Complexity
  
  Volume: in press
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems2014
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Theory of Computing Systems
  
  Volume: in press Issue: 1 Pages: 170-201
- DOI
  10.1007/s00224-013-9518-4
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] One-way reversible and quantum finite automata with advice2014
- Author(s)
  T. Yamakami
- Journal Title
  
  Information and Computation
  
  Volume: 239 Issue: 11 Pages: 611-619
- DOI
  10.1016/j.ipl.2014.05.012
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms2014
- Author(s)
  T. Yamakami
- Journal Title
  
  Proceedings of the Joint 7th International Conference on Soft Computing and Intelligent Systems and 15th International Symposium on Advanced Intelligent Systems
  
  Volume: 2014 Pages: 29-35
- DOI
  10.1109/scis-isis.2014.7044695
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata (extended abstract)2014
- Author(s)
  T. Yamakami
- Journal Title
  
  Proceedings of the 15th Italian Conference on Theoretical Computer Science, CEUR Workshop Proceedings
  
  Volume: 1231
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)2014
- Author(s)
  T. Yamakami
- Journal Title
  
  Proceedings of the 8th IFIP International Conference on Theoretical Computer Science, Lecture Notes in Computer Science
  
  Volume: 8705 Pages: 136-150
- DOI
  10.1007/978-3-662-44602-7_12
- ISBN
  9783642387081, 9783642387098
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages2014
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science
  
  Volume: 8327 Pages: 514-525
- DOI
  10.1007/978-3-319-04298-5_45
- ISBN
  9783319042978, 9783319042985
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Quantum and Reversible Verification of Proofs Using Constant Memory Space2014
- Author(s)
  Marcos Villagra and Tomoyuki Yamakami
- Journal Title
  
  Lecture Notes in Computer Science
  
  Volume: 8890 Pages: 144-156
- DOI
  10.1007/978-3-319-13749-0_13
- ISBN
  9783319137483, 9783319137490
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-13J06353, KAKENHI-PROJECT-24500011
[Journal Article] Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems2013
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 7th Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science
  
  Volume: 8287 Pages: 318-329
- DOI
  10.1007/978-3-319-03780-6_28
- ISBN
  9783319037790, 9783319037806
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] The dissecting power of regular languages2013
- Author(s)
  Tomoyuki Yamakami and Yuichi Kato
- Journal Title
  
  Information Processing Letters
  
  Volume: 113 Issue: 4 Pages: 116-122
- DOI
  10.1016/j.ipl.2012.12.006
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs2012
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 447 Pages: 120-135
- DOI
  10.1016/j.tcs.2012.03.036
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Computational indistinguishability between quantum states and its cryptographic application2012
- Author(s)
  Akinori Kawachi. Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami
- Journal Title
  
  Journal of Cryptology
  
  Volume: 25 Issue: 3 Pages: 528-555
- DOI
  10.1007/s00145-011-9103-4
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems2012
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 461 Pages: 86-105
- DOI
  10.1016/j.tcs.2011.11.037
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Constant unary constraints and symmetric real-weighted counting CSPs2012
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 23rd International Symposium on Algorithms and Computation, Lecture Notes in Computer Science
  
  Volume: 7676 Pages: 237-246
- DOI
  10.1007/978-3-642-35261-4_27
- ISBN
  9783642352607, 9783642352614
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Approximate counting for complex-weighted Boolean constraint satisfaction problems2012
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Information and Computation
  
  Volume: 219 Pages: 17-38
- DOI
  10.1016/j.ic.2012.08.002
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] One-way reversible and quantum finite automata with advice2012
- Author(s)
  Tomoyuki Yamakami
- Journal Title
  
  Proceedings of the 6th International Conference on Language and Automata Theory and Applications, Lecture Notes in Computer Science
  
  Volume: 7183 Pages: 526-537
- DOI
  10.1007/978-3-642-28332-1_45
- ISBN
  9783642283314, 9783642283321
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-24500011
[Journal Article] Quantum hardcore functions by complexity-theoretical list decoding2010
- Author(s)
  A.Kawachi, T.Yamakami
- Journal Title
  
  SIAM Journal on Computing 39
  
  Pages: 2941-2969
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500015
[Journal Article] Theory of one tape linear time Turing machines2010
- Author(s)
  K.Tadaki, T.Yamakami, J.C.H.Lin
- Journal Title
  
  Theoretical Computer Science 411
  
  Pages: 22-43
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500015
[Journal Article] An application of quantum finite automata to interactive proof systems2009
- Author(s)
  Harumichi Nishimura, Tomoyuki Yamakami
- Journal Title
  
  Journal of Computer and System Sciences 75(4)
  
  Pages: 255-269
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500015
[Journal Article] 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
- Author(s)
  T. Yamakami
- Journal Title
  
  A conference version appeared in ISAAC 2009, Lecture Notes in Computer Science Vol. 5878
  
  Pages: 933-942
- Data Source
  KAKENHI-PROJECT-19500015
[Journal Article] Quantum Merlin-Arthur proof systems : are multiple Merlins more helpful to Arthur?2009
- Author(s)
  H.Kobayashi, K.Matsumoto, T.Yamakami
- Journal Title
  
  Chicago Journal of Theoretical Computer Science 2009
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500015
[Journal Article] The efficiency of quantum identity testing of multiple states2008
- Author(s)
  Masaru Kada, Harumichi Nishimura, Tomoyuki Yamakami
- Journal Title
  
  Journal of Physics A : Mathematical and Theoretical 41(3)
  
  Pages: 395309-395309
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500015
[Presentation] When Input Integers are Given in the Unary Numeral Representation (Preliminary Report)2023
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会コンピュテーション研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] When input integers are given in the unary numeral representation -- (preliminary report) --2023
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会コンピュテーション研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report)2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会　情報理論研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Nondeterministically selecting positive instances of context-free languages2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The 22nd Italian Conference on Theoretical Computer Science
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-k storage automata2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The 27th International Computing and Combinatorics Conference
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Synchronizing words for real-time deterministic pushdown automata2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The 7th International Conference on Mathematics and Computing
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report)2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会　情報理論研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Synchronizing Words for Real-Time Deterministic Pushdown Automata2021
- Author(s)
  Tomoyuki Yamakami, Eitatsu Mikami
- Organizer
  The 7th International Conference on Mathematics and Computing
- Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The 19th International Conference on Unconventional Computation and Natural Computation
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Fuzzy Kolmogorov complexity based on fuzzy decompression algorithms and its application to fuzzy data mining2021
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The 17th International Conference on Advanced Data Mining and Applications
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] シンクロナイジングプッシュダウンオートマトンとリセットワード2020
- Author(s)
  三神栄達・山上智幸
- Organizer
  電子情報通信学会コンピュテーション研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] What Restrictions Naturally Allow Well-Known NP-Complete Problems to Yield NL-Completeness and the Linear Space Hypothesis?2020
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会コンピュテーション研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Type-2 Computability, Generic Oracles, and the Linear Space Hypothesis2019
- Author(s)
  Tomoyuki Yamakami
- Organizer
  Higher-order Complexity Theory and its Applications
- Invited / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] 書き換え制限付き決定性オートマトンと繰り返し補題2019
- Author(s)
  吉田光星・山上智幸
- Organizer
  電子情報通信学会コンピュテーション研究会
- Data Source
  KAKENHI-PROJECT-19K11820
[Presentation] Non-uniform state complexity of quantum finite automata and quantum polynomial-time logarithmic-space computation with quantum advice -- (preliminary report) --2018
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会量子情報技術研究会（QIT）
- Data Source
  KAKENHI-PROJECT-16K00013
[Presentation] State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis2018
- Author(s)
  Tomoyuki Yamakami
- Organizer
  情報処理学会アルゴリズム研究会（SIGAL）
- Data Source
  KAKENHI-PROJECT-16K00013
[Presentation] The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms (preliminary report)2014
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会コンピュテーション研究会
- Place of Presentation
  豊橋技科大
- Year and Date
  2014-09-02
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] The state complexity of two-way quantum finite automata (preliminary report)2014
- Author(s)
  Marcos Villagra and Tomoyuki Yamakami
- Organizer
  電子情報通信学会コンピュテーション研究会
- Place of Presentation
  中央大学
- Year and Date
  2014-10-08
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] Non-Interactive Proof Verification Procedures of Reversible and Quantum Finite Automata2014
- Author(s)
  Marcos Villagra and Tomoyuki Yamakami
- Organizer
  情報処理学会、アルゴリズム研究会
- Place of Presentation
  中央大学後楽園キャンパス
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] Constant-Space Zero-Knowledge Proofs Systems with One-Way Quantum Verifiers (Preliminary Report)2013
- Author(s)
  Marcos Villagra and Tomoyuki Yamakami
- Organizer
  電子情報通信学会、コンピュテーション研究会
- Place of Presentation
  名古屋工業大学
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] Approximation classification of complex-weighted counting CSPs2013
- Author(s)
  Tomoyuki Yamakami
- Organizer
  Dagstuhl Seminar 13031- Computational Counting, Schloss Dagstuhl, Leibniz-Zentrum für Informatik
- Place of Presentation
  Schloss Dagstuhl, Germany
- Invited
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages (Preliminary Version)2013
- Author(s)
  Tomoyuki Yamakami
- Organizer
  電子情報通信学会、コンピュテーション研究会
- Place of Presentation
  鳥取環境大学
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] Nondeterministic pushdown automata with write-only output tapes and definable function classes2012
- Author(s)
  Tomoyuki Yamakami
- Organizer
  情報処理学会　第142回アルゴリズム研究会
- Place of Presentation
  岩手大学
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] The dissecting power of regular languages2012
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The 15th Japan-Korea Joint Workshop on Algorithms and Computation
- Place of Presentation
  国立情報学研究所、東京
- Data Source
  KAKENHI-PROJECT-24500011
[Presentation] Quantum finite automata with advice2009
- Author(s)
  T. Yamakami
- Organizer
  情報処理学会、第127回アルゴリズム研究会
- Place of Presentation
  名古屋大学
- Data Source
  KAKENHI-PROJECT-19500015
[Presentation] The role of advice to linear-time Turing machines and finite automata2009
- Author(s)
  Tomoyuki Yamakami
- Organizer
  Proc.20th International Symposium on Algorithms and Computing(ISAAC 2009)
- Place of Presentation
  Honolulu, Hawaii, USA
- Year and Date
  2009-12-18
- Data Source
  KAKENHI-PROJECT-19500015
[Presentation] Quantum finite automata with advice2009
- Author(s)
  Tomoyuki Yamakami
- Organizer
  情報処理学会第127回アルゴリズム研究会
- Place of Presentation
  名古屋大学
- Year and Date
  2009-11-27
- Data Source
  KAKENHI-PROJECT-19500015
[Presentation] Multiple Quantum Zero-Knowledge Proofs with Constant Space Verifiers2007
- Author(s)
  Tomoyuki Yamakami
- Organizer
  The Fourth Central European Quantum Information Processing Workshop (CEQIP 2007)
- Place of Presentation
  Valtice, Czech Republic
- Year and Date
  2007-06-27
- Data Source
  KAKENHI-PROJECT-19500015
[Presentation] Quantum list decoding from quantumly corrupted codewords for classical block codes of polynomially small rate2007
- Author(s)
  T. Yamakami
- Organizer
  Proceedings of the Thirteenth Computing : The Australasian Theory Symposium (CATS 2007)
- Place of Presentation
  Ballarat, Australia
- Data Source
  KAKENHI-PROJECT-19500015

1. VILLAGRA Marcos

# of Collaborated Projects: 0 results

# of Collaborated Products: 2 results

YAMAKAMI TOMOYUKI 山上 智幸

山上 智幸 ヤマカミ トモユキ

YAMAKAMI Tomoyuki 山上 智幸

Research Projects

Research Products

Co-Researchers

Characterization of quantum computing using quantum recursive functions and quantum logics and its application to quantum software developmentPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Efficient use of memory space by data processing algorithms on compact-size devicesPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

An Analysis of Memory Space Usage by Algorithms Solving NL Search ProblemsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

How to select constraints that help algorithms approximately solve constraint satisfaction problemsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

An Analysis of Quantum Interactive Proofs and Their Application to Quantum CryptographyPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

[Journal Article] Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] When input integers are given in the unary numeral representation2023

Author(s)

Journal Title

Data Source

[Journal Article] The 2CNF Boolean formula satisfiability problem and the linear space hypothesis2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Synchronizing deterministic push-down automata can be really hard2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Power of counting by nonuniform families of polynomial-size finite automata2023

Author(s)

Journal Title

DOI

ISBN

Data Source

[Journal Article] Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits (Extended Abstract)2022

Author(s)

Journal Title

DOI

ISBN

Data Source

[Journal Article] Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice2022

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report)2022

Author(s)

Journal Title

DOI

ISBN

Data Source

[Journal Article] Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis2022

Author(s)

YAMAKAMI TOMOYUKI 山上智幸

山上智幸ヤマカミトモユキ

YAMAKAMI Tomoyuki 山上智幸