Hermann Gruber's user avatar
Hermann Gruber's user avatar
Hermann Gruber's user avatar
Hermann Gruber
  • Member for 13 years, 5 months
  • Last seen this week
2 votes

Modify DCFG to enforce length limit

2 votes

Is it useful to "untangle" an NFA by converting to a regular expression and back

5 votes

Relationship between size of Boolean functions and DFAs

7 votes
Accepted

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

5 votes

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

3 votes

What are some examples of decidable Natural Problems outside of EEXP?

4 votes

Problems complete for non-deterministic PSPACE

4 votes

General collection with the current state of complexity bounds of well-known unsolved problems?

9 votes
Accepted

Is DFA language inclusion decidable in quasi-linear time?

3 votes

Defining regular language classes with disjoint union

4 votes

Is there any context-free language that is inherently ambiguous as an indexed language

5 votes

Is there any inherently ambiguous indexed language?

2 votes

Complexity of Yao's tiling number?

6 votes
Accepted

Alternative to LBA for recognising context-sensitive languages

2 votes

When should one start looking at existing results in theoretical CS?

4 votes

Status of certain problems in knot theory

13 votes
Accepted

Ambiguity of regular expressions

1 vote

Where and how did computers help prove a theorem?

1 vote

Where and how did computers help prove a theorem?

3 votes

Different definitions of grammar complexity

8 votes
Accepted

Survey on Erdős-Pósa?

9 votes

Planarity of planar finite automata intersection

14 votes
Accepted

When was co-NP introduced for the first time?

4 votes

Where to find info on (polytime) approximability of various discrete optimization problems?

7 votes

Lengths of "all-accepted" words in Context Free languages

11 votes

In the neutral zone between polynomial and sub-exponential

4 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

5 votes
Accepted

What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search?

4 votes

Applications of sunflower lemma in theoretical computer science

4 votes

NP-complete decision problems on deterministic automata