Denis's user avatar
Denis's user avatar
Denis's user avatar
Denis
  • Member for 12 years
  • Last seen this week
4 votes

Is there a simple game with asymmetric complexity?

4 votes

Hard-looking algorithmic problems made easy by theorems

3 votes

Total orders which are the transitive closure of a set in P

3 votes
Accepted

Difference between infinite state machines and turing machines

3 votes

Simplification of weighted NFA

3 votes

Chomsky hierarchy for tree structures

3 votes
Accepted

Giving a finite collection of infinite words "complex" enough with respect to automata measure

3 votes

Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

3 votes

Is there a generalization of the GO game that is known to be Turing complete?

3 votes
Accepted

Has this form of "kind-of-dual" homomorphisms been studied?

3 votes
Accepted

An exponentially-ambiguous weighted automaton without an equivalent polynomially-ambiguous automaton

3 votes

Example of R and G when $R \subseteq L(G)$ is undecidable

3 votes

Are there decidable problems for which for no algorithm we can give time bounds?

3 votes

Is modal $\mu$-calculus "equivalent" to bisimulation?

3 votes
Accepted

Is every countable, finite-branching LTS bisimilar to a tree?

2 votes
Accepted

Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

2 votes
Accepted

Max Sum Product Multi-objective Shortest path problem

2 votes

Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

2 votes

Prefix Probability in Stochastic Languages

2 votes
Accepted

Regular safety properties and bad prefixes of $\omega$-regular properties

2 votes

Progress on generalized star-height problem?

2 votes

What is the complexity of the equivalence problem for read-once decision trees?

2 votes

Explaining computer science algorithms/concepts/ideas using metaphors

2 votes

Equivalent formula for LTL with and without past operators

2 votes

How are safety/liveness languages defined on the set of finite or infinite words?

2 votes

Binary matrix column subset selection complexity

2 votes

Why does IFP< not capture PTIME?

2 votes

Bounds on the size of NFA for $r$-skip $k$-distinct language

2 votes

Completeness of the extension of first order logic with least fixed point order operator

1 vote
Accepted

The polynomial languages and ordered syntactic monoids