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 ...


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 ...


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 ...


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 ...


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).


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