Skip to main content
Cilenco's user avatar
Cilenco's user avatar
Cilenco's user avatar
Cilenco
  • Member for 8 years, 11 months
  • Last seen more than a month ago
  • Germany
6 votes
1 answer
2k views

How to prove the emptiness of intersection of two context free languages is undecidable?

5 votes
1 answer
131 views

Problem with definition of bisimilarity

3 votes
2 answers
3k views

Show that NP is not equal to SPACE(n)

3 votes
0 answers
33 views

Automaton without stack for visibly pushdown languages

3 votes
1 answer
119 views

Nested word automatons

3 votes
1 answer
307 views

Proof emptiness for PDA is $\mathcal{O}(n^3)$

2 votes
1 answer
129 views

Is a Petri net without places well-defined?

2 votes
2 answers
337 views

Why is LTL Model Checking in PSPACE

1 vote
1 answer
183 views

Efficiently deciding whether TM accepts all inputs in at most $k$ steps

0 votes
1 answer
223 views

Model Checking CTL* algorithm

0 votes
0 answers
103 views

Space complexity for accepting word decision problem of DFAs