research
∙
06/21/2022
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis
The concept of space-bounded computability has become significantly impo...
share
research
∙
03/18/2022
Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
The closure of deterministic context-free languages under logarithmic-sp...
research
∙
12/17/2021
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
We study the computational complexity of finite intersections and unions...
research
∙
11/09/2021
Behavioral Strengths and Weaknesses of Various Models of Limited Automata
We examine the behaviors of various models of k-limited automata, which ...
research
∙
11/04/2021
The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
In various models of one-way pushdown automata, the explicit use of two ...
research
∙
08/29/2021
Parameterizations of Logarithmic-Space Reductions, Stack-State 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...
research
∙
05/04/2020
Synchronizing Deterministic Push-Down Automata Can Be Really Hard
The question if a deterministic finite automaton admits a software reset...
research
∙
01/15/2020
How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
Quantum computation has emerged as a powerful computational medium of ou...
research
∙
07/05/2019
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
The state complexity of a finite(-state) automaton intuitively measures ...
research
∙
03/18/2019
One-Way Topological Automata and the Tantalizing Effects of Their Topological Features
We cast new light on the existing models of 1-way deterministic topologi...
research
∙
01/17/2019
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P
We focus our attention onto polynomial-time sub-linear-space computation...
research
∙
11/15/2018
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis
The linear space hypothesis is a practical working hypothesis, which ori...
research
∙
02/07/2018
A Schematic Definition of Quantum Polynomial Time Computability
In the past four decades, the notion of quantum polynomial-time computab...
research
∙
09/29/2017
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
We aim at investigating the solvability/insolvability of nondeterministi...
research
∙
09/10/2015