I would like to prove (or disprove) the following conjecture: Conjecture: a two counter automata (2CA) cannot decide the following language: $L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$ A 2CA can easily check if the binary representatio...
think the se chat rooms are sufficient for many types of collaborative work & its more the lack of use/ imagination that limits collaboration possibiities of the site right now. very nice to see your question jump the hurdle to some degree.
This question builds on a comment of Shane's in a previous meta post on what can be achieved using a theory Q&A site. I've spent a good deal of time on Jeff Erickson's lovely problem about unshuffling a string, and during the proposal phase, on his question about the complexity of minimum sequen...
In their latest blog post, the guys from tex.SE mention that they regularly hold events where they specificly sift through the list of open questions with the goal to answer as many of them as possible. As we have about the same number of open questions as they have, we should ask ourselves: Can...
One of the things that regularly prompts me to refresh this stackexchange is the promise of interesting open problems (and not "wide" open problems like major complexity class separations or the complexity of factoring/matrix multiplication/etc). Encoded in this are three qualities I am looking ...
« first day (569 days earlier) ← previous day next day → last day (3060 days later) »