3 papers
cs.CC2025
Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
Tomoyuki Yamakami
Syntactic NL or succinctly SNL was first introduced in 2017, analogously to SNP, as a ``syntactically''-defined natural subclass of NL (nondeterministic logarithmic-space complexit…
quant-ph2025
Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
Tomoyuki Yamakami
We introduce a quantum analogue of classical first-order logic (FO) and develop a theory of quantum first-order logic as a basis of the productive discussions on the power of logic…
cs.CC2024
Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
Tomoyuki Yamakami
We discuss a nondeterministic variant of the recently introduced machine model of deterministic auxiliary depth- storage automata (or aux--sda's) by Yamakami. It was proven t…