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 ...
Andrej Bauer's user avatar
  • 28.8k
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 ...
Denis's user avatar
  • 8,678
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 ...
Michael Kay's user avatar
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 ...
Joshua Grochow's user avatar
10 votes
Accepted

Converting 2-ambiguous NFA to unambiguous NFA

I think that this is in fact not possible, thanks to the (recent and difficult!) ICALP'22 results of Göös et al.. They show that there are UFAs $A_1$ and $A_2$ with $n$ states such that the language $...
a3nm's user avatar
  • 9,232
8 votes
Accepted

Error in Robson's proof about separating strings?

Converting my comment to an answer: This is taken care of in the paragraph just before Theorem 1. If the accepting state is reached at some $v_j$, then we necessarily have $j>i$, and we can compose ...
Tassle's user avatar
  • 871
7 votes
Accepted

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

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying ...
Hermann Gruber's user avatar
6 votes
Accepted

Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?

You can solve this using Parikh's theorem. We want to prove that the set $A = \{(a, b)\in\mathbb{N_{>0}}^2 | a-b\sqrt2 \geq 0\} = \{(a,b)\in\mathbb{N_{>0}}^2 | \frac ab\geq\sqrt2\}$ isn't ...
Command Master's user avatar
5 votes

Relationship between size of Boolean functions and DFAs

Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes. Maximum and average state ...
Hermann Gruber's user avatar
5 votes

Relationship between size of Boolean functions and DFAs

Regarding question 3: There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation ...
Yuval Filmus's user avatar
  • 14.4k
5 votes

Relationship between size of Boolean functions and DFAs

Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself. No. Consider $f$ defined by $f(x)=1$ iff $x_1 \ne x_{n/2+1}$ or $x_2 \ne x_{n/2+2}$ or ...
D.W.'s user avatar
  • 12k
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: ...
Bartosz Bednarczyk's user avatar
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 ...
Denis's user avatar
  • 8,678
4 votes

Logical Equivalents of Finite State Transducers

By a transducer I assume you mean an automaton which can print output on transitions. The extensional equivalence between deterministic and nondeterministic automata as well as 1-way and 2-way ...
Siddharth's user avatar
  • 823
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 ...
A7exSchin's user avatar
  • 141
4 votes

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

Minimization of automata on infinite words is still a very mysterious problem. Although most of the results are negative, as pointed by Shaull, for example, minimization of DBWs (deterministic Büchi ...
Bader Abu Radi's user avatar
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)$...
Janmar's user avatar
  • 135
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 ...
StefanH's user avatar
  • 2,077
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 ...
AnoE's user avatar
  • 219
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 ...
Johannes Bauer's user avatar
2 votes
Accepted

Are regular expressions polynomially decomposable?

The answer to my question turned out to be positive, which follows from a translation from regular expressions to automata and back. Check the answer of Hermann Gruber to my previous POST.
Bartosz Bednarczyk's user avatar
2 votes
Accepted

What is the current state of the art on exact identification of DFAs with a maximum N states

The last step of the proposed reasoning can be done as described in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain and in ...
EXPTIME-complete's user avatar
2 votes

Obscure characterizations of the regular languages

A language is regular if and only if it is linearly separable by the DFA kernel, defined here: How many DFAs accept two given strings? This is Theorem 11 in https://www.sciencedirect.com/science/...
Aryeh's user avatar
  • 10.5k
2 votes

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

In fact, this roundtrip conversion is used in the proof of the Star Height Lemma, and this in turn has lots of implications in the area of descriptional complexity of regular expressions. And here it ...
Hermann Gruber's user avatar
2 votes

Obscure characterizations of the regular languages

I think this one may fit the bill: A language is regular if and only if its characteristic series is the support of an $\mathbb{N}$-rational series. Definitions. Let $\Sigma$ be an alphabet and $\...
Ekene E.'s user avatar
  • 121
2 votes

Obscure characterizations of the regular languages

Here are fun ones: computational interpretations of circular proofs for Kleene algebra in linear logic, see https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45 (Theorem 24) ...
Denis's user avatar
  • 8,678
1 vote

What is the intution on the TTT algorithm for regular grammar inference?

If you get a counterexample back from the teacher the counterexample is very long. If the suffix analysis is used as described in the paper, the suffix can be very long, this suffix is added in the ...
Coping Forever's user avatar
1 vote
Accepted

Counting the different subsets of nodes seen when iterating a subset through a directed graph

The argument in Chrobak’s paper can be applied to this problem as well, with the same bounds. Let $\{D_i:i<k\}$ be the set of strongly connected components of $G$ that contain a cycle (i.e., other ...
Emil Jeřábek's user avatar
1 vote

Pumping lemma for CFL intersection

The language $L_t=\{a_1^na_2^n\dots a_t^n:n\ge 0, a_i=a$ for odd $i$ and $a_i=b$ for even $i\}$ is the intersection of two CFL's, even $\cup_t~L_t$ is, and it is hard to imagine what kind of pumping ...
domotorp's user avatar
  • 13.8k
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 ...
Max Flow's user avatar
  • 193

Only top scored, non community-wiki answers of a minimum length are eligible