New answers tagged reference-request
0
For Automata Theory, get the 1979 edition of "Automata Theory, Languages and Computation". Unlike the 3rd edition, it is not an introductory book, but goes into lots of detail about all the specifics of automata theory. It covers things like trios, cones, abstract families of languages, etc. that most undergrad books skip.
2
In computer algebra, this computation is usually referred as computing the subproduct tree and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. Modern Computer Algebra, 3rd edition, 2013 [chapter 10]. As far as I know, the best known complexity is $O(\mathsf{M}(n)\log n)$ where $\mathsf M(n)$ denotes the ...
6
The paper Ambiguity in Graphs and Expressions (Book et al., 1971) discusses constructing regular expressions that preserve the ambiguity of the input NFA and vice versa.
That is, they give a definition for "ambiguity" in regular expressions (how many valid parses are there for a given word), and show how to construct an NFA that will have the same ...
4
To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known to be NP-hard.
The crossing number of a knot/link is not known to be in NP (even if you give me the diagram with the fewest crossings I would need to solve the ...
4
Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial: https://doi.org/10.1017/S0305004100068936
On the positive side, this problem is fixed-parameter tractable:
https://arxiv.org/abs/1712.05776
Regarding the unknotting problem, Marc Lackenby ...
3
Denis's excellent answer mentions that aperiodicity is orthogonal to safety, so as long as this is allowed, one can also take a topological view instead of a purely algebraic:
Safety languages can be characterized as the closed sets in a natural topology over infinite words (https://link.springer.com/content/pdf/10.1007%2F978-3-642-58041-3_5.pdf)
Thus, the ...
6
On infinite words, automata are much more convenient than Wilke algebra (playing the role of monoids) to characterize safety. Indeed, it just corresponds to being accepted by an automaton where all runs are accepting. This is because automata are designed to append new content to the right, while in Wilke Algebra you can more naturally append to the left.
If ...
1
So we ended up calling this quantity the $\alpha$th moment of information and proving some inequalities about it:
https://arxiv.org/abs/2004.12680
(paper to appear in the NIPS 2021 conference).
3
Edit from discussion in comments below: There are two related questions here. One is "What languages can be described by Diophantine polynomials with polynomially-bounded inputs?" This is the complexity class $D$, described in this answer. The other is "What is the complexity of the decision problem of whether a Diophantine polynomial has a ...
Top 50 recent answers are included