49 citations · 281 across the 55 of their papers we have counts for
60 papers
Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
Tomoyuki Yamakami
Nonuniform families of polynomial-size finite automata and pushdown automata respectively have strong connections to nonuniform-NL and nonuniform-LOGCFL. We examine the behaviors o…
Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
Tomoyuki Yamakami
We study the computational complexity of counting constraint satisfaction problems (#CSPs) whose constraints assign complex numbers to Boolean inputs when the corresponding constra…
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata
Tomoyuki Yamakami
Nonuniform families of polynomial-size finite automata, which are series of indexed finite automata having polynomially many inner states, are used in the past literature to solve…
Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
Tomoyuki Yamakami
Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time…
Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
Tomoyuki Yamakami
Lately, there have been intensive studies on strengths and limitations of nonuniform families of promise decision problems solvable by various types of polynomial-size finite autom…
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis
Tomoyuki Yamakami
The concept of space-bounded computability has become significantly important in handling vast data sets on memory-limited computing devices. To replenish the existing short list o…