25
votes
Theoretical Computer Science vs other Sciences?
As a theoretical computer scientist I am proud of the following achievements of the field.
Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
- 28.3k
18
votes
Theoretical Computer Science vs other Sciences?
As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer.
We must also keep in mind that it ...
- 8,598
11
votes
Theoretical Computer Science vs other Sciences?
I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly ...
- 211
10
votes
Theoretical Computer Science vs other Sciences?
My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics.
I'll also point out that you ...
- 36.9k
9
votes
Accepted
Is DFA language inclusion decidable in quasi-linear time?
EDIT: the question has an answer by Michael Wehar. A better than quadratic running time contradicts the strong exponential time hypothesis.
https://cstheory.stackexchange.com/a/29166/2367
ORIGINAL ...
- 5,840
6
votes
Accepted
Formalization of matching logic (logic behind K Framework)
There is a number of formalizations of matching logic in various proof assistants. I am a co-author of the first one in the following list; thus I have more insight into that one. I am not aware of ...
- 176
5
votes
Accepted
Deciding finiteness of regular language is NL-complete?
Let $\mathcal{A}$ be an NFA. We say that a state $q$ lies on a cycle if there is a non-empty path from $q$ to $q$ in the graph of $\mathcal{A}$. In my answer I assume that the following lemma is true:
...
- 1,340
4
votes
Theoretical Computer Science vs other Sciences?
Maybe I can offer some interesting point of view here:
I finished my Bachelors degree in physics and started a bachelors degree in software engineering afterwards. People often ask me why, which the ...
- 141
4
votes
Accepted
Complexity of the inevitability problem over monoids
I think it is PSpace-complete, here is a proof scheme.
We can go back to the proof scheme for PSpace-completeness of regular expression universality, e.g. described in this answer.
There we can see ...
- 8,598
3
votes
Generating grammar from a string
You might be interested in Sequitur (given a single string, it compresses it by finding a grammar that generates just that one string) or in grammar induction (given a set of strings, it finds a ...
- 11.7k
3
votes
Accepted
What is the solution of this equation on regular languages?
$L$ is regular. I'll prove this for $n=1$; then it follows for arbitrary $n$, as the intersection of regular languages is itself regular.
Define
$$L = \{x \in \Sigma^* \mid \{x\} \cdot A \subseteq B\}...
- 11.7k
3
votes
Theoretical Computer Science vs other Sciences?
I recently saw a video of Richard Feynman (the famous physicist), in which he explains a bunch of physical phenomena. It’s on youtube, it‘s a famous one, and it completely blew my mind and it just got ...
- 2,037
3
votes
Theoretical Computer Science vs other Sciences?
I have worked in IT for 27'ish years, and studied CS in Germany as well; even at a more theoretical uni (there was a separate "technical" uni in our city which got to do all the robotics ...
- 219
3
votes
NP-complete decision problems on deterministic automata
Consider the following problem:
Given two DFAs $A_1, A_2$ and an integer $k\in\mathbb{N}$. Decide whether there is a $k$-state DFA $A_{sep}$ such that $\mathcal{L}(A_{sep}) \subseteq \mathcal{L}(A_1)$...
- 135
2
votes
Can an unrestricted grammar have a rule with only terminals on the left-hand side?
No, an unrestricted grammar cannot have a rule with only terminals on the left-hand side. In formal grammar, a production rule is written in the form of:
α → β
where α and β are strings of symbols, ...
2
votes
Theoretical Computer Science vs other Sciences?
Back in college, I loved TCS for the mental gymnastics. I'd argue that, for better or worse, they shaped the way my mind works: I'm a decent programmer and, generally, technologist and I think that's ...
- 121
1
vote
Formalization of matching logic (logic behind K Framework)
I'm currently at the end of my PhD thesis about the interoperability of semantics. That's the reason I'm studying the translation from the semantical framework K into the logical framework Dedukti.
...
1
vote
Theoretical Computer Science vs other Sciences?
It seems that your education has sparked (or noticeably deepened) your fascination for theory in general, a fascination you can experience and build upon in the field of TCS and could experience and ...
- 193
1
vote
Theoretical Computer Science vs other Sciences?
There is a tension between theory and praxis in any discipline. In TCS, many ideas that are cooked up in labs as products of research and development eventually surface 20 years later in industry. ...
- 111
1
vote
Proper terminology for input, parameter or variable fixing. Refinement? Projection? Fixation? Partial valuation?
"Fixing" inputs or parameters to specific values can be a valid approach, but it may not be the most appropriate term to use depending on the context. "Refining" a specification ...
- 11
1
vote
Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?
It is not known whether CFL is contained in space o(log^2(n)). If CFL were contained in space o(log^2(n)), then NL would also be contained in space o(log^2(n)). The question whether NL is contained in ...
- 19
Only top scored, non community-wiki answers of a minimum length are eligible