
Parameterizations of LogarithmicSpace Reductions, StackState Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question
The complexity class LOGCFL (resp., LOGDCFL) consists of all languages t...
read it

Synchronizing Deterministic PushDown Automata Can Be Really Hard
The question if a deterministic finite automaton admits a software reset...
read it

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
Quantum computation has emerged as a powerful computational medium of ou...
read it

Nonuniform Families of PolynomialSize Quantum Finite Automata and Quantum LogarithmicSpace Computation with PolynomialSize Advice
The state complexity of a finite(state) automaton intuitively measures ...
read it

OneWay Topological Automata and the Tantalizing Effects of Their Topological Features
We cast new light on the existing models of 1way deterministic topologi...
read it

Supportive Oracles for Parameterized PolynomialTime SubLinearSpace Computations in Relation to L, NL, and P
We focus our attention onto polynomialtime sublinearspace computation...
read it

State Complexity Characterizations of Parameterized DegreeBounded Graph Connectivity, SubLinear Space Computation, and the Linear Space Hypothesis
The linear space hypothesis is a practical working hypothesis, which ori...
read it

A Schematic Definition of Quantum Polynomial Time Computability
In the past four decades, the notion of quantum polynomialtime computab...
read it

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
We aim at investigating the solvability/insolvability of nondeterministi...
read it

The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms
We reexamine a practical aspect of combinatorial fuzzy problems of vari...
read it
Tomoyuki Yamakami
is this you? claim profile