user avatar
user avatar
user avatar
Abuzer Yakaryilmaz
  • Member for 10 years, 8 months
  • Last seen more than a week ago
16 votes

Complexity of a variant of the max word problem. NP-complete?

15 votes
Accepted

A "simple" language outside $CFL \cup coCFL$?

12 votes
Accepted

Landscape of interactive proof systems

12 votes

On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

12 votes
Accepted

Bounds on size of self-concatenation of Finite Languages

11 votes
Accepted

Is there a survey of the field of quantum automata?

9 votes
Accepted

Introduction to probabilistic automata

9 votes
Accepted

2DFA that requires many states in equivalent DFA?

9 votes

Papers every complexity theorist should read

8 votes
Accepted

Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?

7 votes
Accepted

Nonregular Languages in Sublogarithmic Space

6 votes

Applications of $p$-adic numbers in CS

5 votes
Accepted

Two way deterministic multihead counter automata or logspace TM with counter

5 votes
Accepted

What class of languages is recognized by finite-state automata with $k$ heads?

5 votes

Which results make quantum space interesting?

4 votes
Accepted

Complexity of a variant of the max word problem. NP-complete?

4 votes
Accepted

Simplest Machine Model for a langauge $ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$

3 votes

Are there non-constructive proofs of existence of "small" Turing machines / NFAs?

3 votes

Resources to learn about the P vs. NP problem

1 vote
Accepted

Super-logspace mapping reducibility

1 vote
Accepted

Interesting SUBSET-SUM problems

0 votes

Palindrome language and Finite Automata Machines