Hermann Gruber
  • Member for 11 years, 2 months
  • Last seen this week
What are the recent TCS books whose drafts are available online?
35 votes

Let me add the following: Analytic Combinatorics, by Flajolet and Sedgewick Codes and Automata (Link Broken), by Berstel, Perrin and Reutenauer

View answer
computing the minimal NFA for a DFA
Accepted answer
28 votes

This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by ...

View answer
The origin of the notion of treewidth
22 votes

In his monograph on graph theory, Reinhard Diestel traces the concept of treewidth and tree decompositions back to a 1976 paper by Halin (albeit not using these names). He also attributes to this ...

View answer
Are there any open problems left about DFAs?
20 votes

I want to point out the another research problem, which concerns the interplay of very basic concepts about DFAs. It is well known that any n-state NFA can be converted into an equivalent DFA having ...

View answer
What is the number of languages accepted by a DFA of size $n$?
Accepted answer
20 votes

I think that this question has been studied previously. Mike Domaratzki wrote a survey on research in this area: "Enumeration of Formal Languages", Bull. EATCS, vol. 89 (June 2006), 113-133: http://...

View answer
Status of Cerny Conjecture?
Accepted answer
19 votes

Trakhtman has a bibliography on the problem, which is apparently kept up to date; so I suppose Černý's question remains unresolved until today. The same is stated in Volkov's recent survey (LATA 2008) ...

View answer
What notable automaton models have polynomially-decidable containment?
Accepted answer
16 votes

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular ...

View answer
When was co-NP introduced for the first time?
Accepted answer
14 votes

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space"...

View answer
What is an unambiguous language in the sense of Schützenberger?
Accepted answer
14 votes

Jean Berstel maintains a website with Schützenberger's collected papers. You can access the original paper (in French) here. A definition of the unambiguous product you are referring to in English is ...

View answer
Ambiguity of regular expressions
Accepted answer
13 votes

Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the ...

View answer
Open access journals
13 votes

The Chicago Journal of Theoretical Computer Science.

View answer
Generating all instances of a regular language up to a certain length
Accepted answer
13 votes

There are several recent papers that address your question, e.g.: Margareta Ackerman and Jeffrey Shallit. Efficient Enumeration of Regular Languages. Conference on Implementation and Application of ...

View answer
Lower bound for NFA accepting 3 letter language
Accepted answer
12 votes

The bounds... We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the ...

View answer
Regular expressions without alternation
Accepted answer
12 votes

The class of regular languages that can be described by regular expressions without union (and without complementation) are known as union-free regular (also: star-dot regular) languages. This class ...

View answer
What are the recent TCS books whose drafts are available online?
12 votes

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi: Tree Automata Techniques and Applications

View answer
Regular expressions: Finding "negation" of regular expression?
Accepted answer
12 votes

As another answer already states, the standard approach is: converting to a DFA, complementing, and converting back to a regular expression takes two exponential steps in the worst case (one for ...

View answer
Funny TCS-related papers etc?
12 votes

A. Broder, J. Stolfi "Pessimal algorithms and simplexity analysis", ACM SIGACT News 16(3), Fall 1984. The paper introduces "an entirely new branch of Computer Science, the design and analysis of ...

View answer
In the neutral zone between polynomial and sub-exponential
11 votes

Parity games have recently been shown to be solvable in quasipolynomial time: https://doi.org/10.1137/17M1145288

View answer
Grid minor in digraphs
Accepted answer
10 votes

There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs. Stephan Kreutzer and Ken-ichi Kawarabayashi: ...

View answer
Practical consequences of $Parity \notin AC^0$
10 votes

I am not an electrical engineer, but search for online patents regarding switching circuits for parity gates, and all proposals (I found patents only until the end of the 1970s) discuss the size-...

View answer
Planarity of planar finite automata intersection
9 votes

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, ...

View answer
Completeness and Context-Sensitive Languages.
Accepted answer
9 votes

To answer your first question, a reducibility fitting your needs is log-lin-reducibility, which is logspace reducibility with the additional constraint that the size of the output string of the ...

View answer
Savitch's use of measurability
Accepted answer
9 votes

I think that this definition is nowadays known under the term space-constructible function. There are functions in sublogarithmic space that are space constructible, while others are not. http://dl2....

View answer
Progress on generalized star-height problem?
9 votes

Regarding your second question, an explanation why the generalized star height problem is less accessible than the star height problem is the following: Already Eggan's seminal paper in 1963 contained ...

View answer
Understanding graph minor theorem
Accepted answer
8 votes

The following book covers some material related to the proof of the graph minor theorem (Chapter 12). Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173. The author ...

View answer
Lengths of "all-accepted" words in Context Free languages
7 votes

The shortest word in $A_L$ is not bounded by a recursive function in the size of a given context-free grammar describing $L$. See here for more results in that direction: https://doi.org/10.4230/...

View answer
Reducing the bandwidth of non-symmetric matrix
Accepted answer
7 votes

The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices. J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal ...

View answer
Taxonomy of notable regular expression automata
Accepted answer
7 votes

Watson (Tech. Rep. Univ. Eindhoven 1995) has written a taxonomy of finite automata construction algorithms; a few more recent developments are found below. For NFAs with epsilon-transitions, the ...

View answer
Alternative to LBA for recognising context-sensitive languages
Accepted answer
6 votes

Here is an alternative model: Benedek Nagy: Left-most derivation and shadow-pushdown automata for context-sensitive languages, ICCOMP'06: Proceedings of the 10th WSEAS international conference on ...

View answer
Is an algorithm with an approximation factor of 4000 useful?
Accepted answer
6 votes

A very good question! While I think a feasible solution which is 4000 times worse than the optimum is often not very practical, if you have several approximation algorithms to choose from, I would ...

View answer