49 citations · 281 across the 55 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
cs.CC2024
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…
cs.CC2024
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…