Tomoyuki Yamakami

Publication Activity (10 Years)

Years Active: 1992-2024
Publications (10 Years): 63

Top Venues

CoRR

Inf. Comput.

DCFS

DLT

Publications

Tomoyuki Yamakami
Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters. CoRR (2024)
Tomoyuki Yamakami
Quantum First-Order Logics that Capture Logarithmic-Time/Space Quantum Computability. CiE (2024)
Tomoyuki Yamakami
Unambiguous and Co-nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters. TAMC (2024)
Tomoyuki Yamakami
Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems. CoRR (2024)
Tomoyuki Yamakami
Logical Expressibility of Syntactic NL for Complementarity and Maximization. WoLLIC (2024)
Tomoyuki Yamakami
Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata. FCT (2023)
Tomoyuki Yamakami
When Input Integers are Given in the Unary Numeral Representation. ICTCS (2023)
Tomoyuki Yamakami
storage automata. Int. J. Comput. Math. Comput. Syst. Theory 8 (1) (2023)
Tomoyuki Yamakami
The 2CNF Boolean formula satisfiability problem and the linear space hypothesis. J. Comput. Syst. Sci. 136 (2023)
Tomoyuki Yamakami
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata. CoRR (2023)
Tomoyuki Yamakami
Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata. CoRR (2023)
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
Synchronizing deterministic push-down automata can be really hard. Inf. Comput. 295 (Part B) (2023)
Tomoyuki Yamakami
Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions. CoRR (2023)
Tomoyuki Yamakami
When Input Integers are Given in the Unary Numeral Representation. CoRR (2023)
Tomoyuki Yamakami
Kolmogorov Complexity Descriptions of the Exquisite Behaviors of Advised Deterministic Pushdown Automata. DLT (2022)
Tomoyuki Yamakami
Formal Grammars for Turn-Bounded Deterministic Context-Free Languages. ICTAC (2022)
Tomoyuki Yamakami
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata. RP (2022)
Tomoyuki Yamakami
Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits - (Extended Abstract). COCOON (2022)
Tomoyuki Yamakami
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis. FTC (1) (2022)
Tomoyuki Yamakami
Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. Inf. Comput. 286 (2022)
Tomoyuki Yamakami
How does adiabatic quantum computation fit into quantum automata theory? Inf. Comput. 284 (2022)
Tomoyuki Yamakami
Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata. CoRR (2022)
Tomoyuki Yamakami
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis. CoRR (2022)
Tomoyuki Yamakami
Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report). ICS (2022)
Tomoyuki Yamakami
Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability. WoLLIC (2022)
Tomoyuki Yamakami
Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question. CoRR (2021)
Tomoyuki Yamakami
Behavioral Strengths and Weaknesses of Various Models of Limited Automata. CoRR (2021)
Tomoyuki Yamakami, Eitatsu Mikami
Synchronizing Words for Real-Time Deterministic Pushdown Automata - Extended Abstract. ICMC (2021)
Tomoyuki Yamakami
Nondeterministically Selecting Positive Instances of Context-Free Languages. ICTCS (2021)
Tomoyuki Yamakami
The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata. CoRR (2021)
Tomoyuki Yamakami
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas. CoRR (2021)
Tomoyuki Yamakami
Fuzzy Kolmogorov Complexity Based on Fuzzy Decompression Algorithms and Its Application to Fuzzy Data Mining - (Preliminary Report). ADMA (2021)
Tomoyuki Yamakami
Quantum Logical Depth and Shallowness of Streaming Data by One-Way Quantum Finite-State Transducers (Preliminary Report). UCNC (2021)
Tomoyuki Yamakami
Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata. COCOON (2021)
Tomoyuki Yamakami
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas. LATA (2020)
Tomoyuki Yamakami
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory? CoRR (2020)
Tomoyuki Yamakami
A Schematic Definition of quantum Polynomial Time Computability. J. Symb. Log. 85 (4) (2020)
Tomoyuki Yamakami
One-Way Topological Automata and the Tantalizing Effects of Their Topological Features. J. Autom. Lang. Comb. 25 (2-3) (2020)
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
Synchronizing Deterministic Push-Down Automata Can Be Really Hard. MFCS (2020)
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
Synchronizing Deterministic Push-Down Automata Can Be Really Hard. CoRR (2020)
Tomoyuki Yamakami
Relativizations of Nonuniform Quantum Finite Automata Families. UCNC (2019)
Tomoyuki Yamakami
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P. TAMC (2019)
Tomoyuki Yamakami
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice. CoRR (2019)
Tomoyuki Yamakami
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P. CoRR (2019)
Tomoyuki Yamakami
Behavioral Strengths and Weaknesses of Various Models of Limited Automata. SOFSEM (2019)
Tomoyuki Yamakami
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice. LATA (2019)
Tomoyuki Yamakami
One-Way Topological Automata and the Tantalizing Effects of Their Topological Features. CoRR (2019)
Tomoyuki Yamakami
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory? DCFS (2019)
Tomoyuki Yamakami
State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis. Theor. Comput. Sci. 798 (2019)
Tomoyuki Yamakami
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis. CoRR (2018)
Tomoyuki Yamakami
A Schematic Definition of Quantum Polynomial Time Computability. CoRR (2018)
Tomoyuki Yamakami
One-way topological automata and the tantalizing effects of their topological features. NCMA (2018)
Tomoyuki Yamakami
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis. DCFS (2018)
Tomoyuki Yamakami
One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity - (Preliminary Report). DLT (2017)
Tomoyuki Yamakami
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis. MFCS (2017)
Tomoyuki Yamakami
A recursive definition of quantum polynomial time computability (extended abstract). NCMA (2017)
Tomoyuki Yamakami
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis. CoRR (2017)
Tomoyuki Yamakami
Parameterized Graph Connectivity and Polynomial-Time Sub-Linear-Space Short Reductions - (Preliminary Report). RP (2017)
Tomoyuki Yamakami
Pseudorandom generators against advised context-free languages. Theor. Comput. Sci. 613 (2016)
Tomoyuki Yamakami
Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions. CoRR (2016)
Tomoyuki Yamakami
Complexity Bounds of Constant-Space Quantum Computation. CoRR (2016)
Tomoyuki Yamakami
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems. CoRR (2016)
Tomoyuki Yamakami
Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords. Balt. J. Mod. Comput. 4 (4) (2016)
Tomoyuki Yamakami
Straight Construction of Non-Interactive Quantum Bit Commitment Schemes from Indistinguishable Quantum State Ensembles. TPNC (2015)
Tomoyuki Yamakami
The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms. CoRR (2015)
Tomoyuki Yamakami
Complexity Bounds of Constant-Space Quantum Computation - (Extended Abstract). DLT (2015)
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
Counting List Matrix Partitions of Graphs. SIAM J. Comput. 44 (4) (2015)
Harumichi Nishimura, Tomoyuki Yamakami
Interactive proofs with quantum finite automata. Theor. Comput. Sci. 568 (2015)
Tomoyuki Yamakami
Structural Complexity of Multi-Valued Partial Functions Computed by Nondeterministic Pushdown Automata. CoRR (2015)
Marcos Villagra, Tomoyuki Yamakami
Quantum State Complexity of Formal Languages. DCFS (2015)
Tomoyuki Yamakami
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems. Theory Comput. Syst. 55 (1) (2014)
Tomoyuki Yamakami
Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata. ICTCS (2014)
Harumichi Nishimura, Tomoyuki Yamakami
Interactive Proofs with Quantum Finite Automata. CoRR (2014)
Tomoyuki Yamakami
The world of combinatorial fuzzy problems and the efficiency of fuzzy approximation algorithms. SCIS&ISIS (2014)
Tomoyuki Yamakami
Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract). IFIP TCS (2014)
Tomoyuki Yamakami
One-way reversible and quantum finite automata with advice. Inf. Comput. 239 (2014)
Marcos Villagra, Tomoyuki Yamakami
Quantum and Reversible Verification of Proofs Using Constant Memory Space. TPNC (2014)
Tomoyuki Yamakami
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages. SOFSEM (2014)
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
Counting List Matrix Partitions of Graphs. Computational Complexity Conference (2014)
Tomoyuki Yamakami
Constant-space quantum interactive proofs against multiple provers. Inf. Process. Lett. 114 (11) (2014)
Tomoyuki Yamakami
Constant-Space Quantum Interactive Proofs Against Multiple Provers. CoRR (2013)
Tomoyuki Yamakami
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems CoRR (2013)
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami
Counting list matrix partitions of graphs. CoRR (2013)
Tomoyuki Yamakami
A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction. CoRR (2013)
Tomoyuki Yamakami, Yuichi Kato
The dissecting power of regular languages. Inf. Process. Lett. 113 (4) (2013)
Tomoyuki Yamakami
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages CoRR (2013)
Tomoyuki Yamakami
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems. COCOA (2013)
Tomoyuki Yamakami
One-Way Reversible and Quantum Finite Automata with Advice. LATA (2012)
Tomoyuki Yamakami
A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs. Theor. Comput. Sci. 447 (2012)
Tomoyuki Yamakami
Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems. Theor. Comput. Sci. 461 (2012)
Tomoyuki Yamakami
Constant Unary Constraints and Symmetric Real-Weighted Counting CSPs. ISAAC (2012)
Tomoyuki Yamakami, Yuichi Kato
The Dissecting Power of Regular Languages CoRR (2012)
Tomoyuki Yamakami
Approximate counting for complex-weighted Boolean constraint satisfaction problems. Inf. Comput. 219 (2012)
Tomoyuki Yamakami
One-Way Reversible and Quantum Finite Automata with Advice CoRR (2012)
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami
Computational Indistinguishability Between Quantum States and Its Cryptographic Application. J. Cryptol. 25 (3) (2012)
Tomoyuki Yamakami
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems. ISAAC (2011)
Tomoyuki Yamakami
Immunity and pseudorandomness of context-free languages. Theor. Comput. Sci. 412 (45) (2011)
Tomoyuki Yamakami
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems. COCOON (2011)
Tomoyuki Yamakami
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems CoRR (2011)
Tomoyuki Yamakami
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems CoRR (2011)

Tomoyuki Yamakami.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Tomoyuki Yamakami