Tag Info

Accepted

Applications of algebraic geometry in type theory/programming language theory

To my knowledge (which is definitely incomplete), there has been relatively little work on this, presumably because it requires assimilating two relatively intricate bodies of knowledge. However, ...
• 32.5k

On the realisation of monoids as syntactic monoids of languages

The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is ...
• 4,831
Accepted

On the realisation of monoids as syntactic monoids of languages

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without ...
• 8,843
Accepted

Are There Highly Symmetric NP- or P-complete Languages?

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-...
• 37.3k
Accepted

What kind of theoretical object corresponds to a C++ concept?

From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to bounded ...
• 16.7k

• 4,831

What category are Tagless Final Algebras final In?

Final Algebra semantics was introduced by Mitch Wand in his paper "Final Algebra Semantics and Data Type Extensions", see this freely available tech report: https://www.cs.indiana.edu/ftp/techreports/...
• 1,675
Accepted

Technical lemma about curves used in original proof of PCP theorem

Notation: Let $P(\langle x_1,\dots,x_k\rangle)$ the set of degree $k$ curves that evaluates to $x_1,\dots,x_k\in\mathbb{F}^m$ at the first $k$ field elements in $\mathbb{F}$ and we will use just $P$ ...
• 397
Accepted

Connection between algebraic logic and computational complexity of logics?

The example you gave extends as follows: SAT for arbitrary lattices (meaning, is a given formula satisfiable in some lattice) is polynomial-time decidable SAT for modular lattices is Turing ...
• 4,485

Reference request: An algebraic characterisation of LTL[XF]-definable word languages

An algebraic characterisation of the restricted temporal logic (fragment using only next and eventually, but not until) is given in [1]. The expressive power of this fragment is the set of regular ...
• 4,831
Accepted

If a root||nonce Proof-of-Work certificate is prime, can it be used in any other interesting proofs?

Heuristically: Yes, I suspect this probably works, if the system of equations is committed to in advance (well before mining works), and if the system of equations is small enough. You'll need the ...
• 12.1k
Accepted

Is the relation decidable?

Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases.
• 4,485
Accepted

Complexity of finding approximate solutions for systems of polynomial equations

The problem is complete for the existential theory of the reals ($\exists\mathbb{R}$). This implies that the problem is NP-hard and can be decided in PSPACE, and there are consequences for the ...
• 131

Uses of algebraic structures in theoretical computer science

In functional programming, the most general and elegant abstractions for problems are often algebraic (or category-theoretic) in nature: monoids, semirings, functors, monads, F-algebras, F-coalgebras, ...
• 1,175

Uses of algebraic structures in theoretical computer science

Recently, we explore (see our paper on springerlink: A formal series-based unification of the frequent itemset mining approaches) a unification attempt to pattern mining (a popular instance of data ...

Computing sum of sparse polynomials squared in O(n log n) time?

Just wanted to note the natural approximation algorithm. This doesn't take advantage of sparsity though. You could use a random sequence $(\sigma_i)_{i\in[n]}$ Taking $X=\sum_i \sigma_i p_i(x)$ we ...
• 958
Complete axiomatization of relation algebras without ${}^-$ and $\top$
The equational theory of the signature $S=\{\vee,\wedge,.,\epsilon,^\smile\}$ is decidable. See this paper by Andréka and Bredikhin. The idea is to associate to every term $t$ over $S$ a graph $G_t$. ...
If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$. But in the beginning of the proof of Lemma 8 they assume without ...