Skip to main content
Share Your Experience: Take the 2024 Developer Survey
14 votes
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, ...
Neel Krishnaswami's user avatar
13 votes

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 ...
J.-E. Pin's user avatar
  • 4,831
12 votes
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 ...
Denis's user avatar
  • 8,893
12 votes
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-...
Joshua Grochow's user avatar
12 votes
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 ...
Dave Clarke's user avatar
  • 16.7k
11 votes

On the realisation of monoids as syntactic monoids of languages

In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check. Definition: Let $M$ be a monoid, and $Y \subseteq ...
Michaël Cadilhac's user avatar
10 votes
Accepted

Chomsky Schützenberger enumeration theorem

There is a proof in the book of Kuich & Salomaa, Semirings, Automata, Languages and another one in the paper of Panholzer, "Gröbner Bases and the Defining Polynomial of a Context-free Grammar ...
Jeffrey Shallit's user avatar
8 votes
Accepted

(N)DFA with same initial/accepting state(s)

This question is solved for deterministic automata and for unambiguous automata in the book [1] [1] J. Berstel, D. Perrin, C, Reutenauer, Codes and automata, Vol. 129 of Encyclopedia of Mathematics ...
J.-E. Pin's user avatar
  • 4,831
7 votes

What's the relationship between "free theorems" and "free objects"

There is no relationship. They both use the word "free", but with different meanings of the word "free". It's just an accidental collision, which will happen when you have a language like English ...
D.W.'s user avatar
  • 12.1k
7 votes
Accepted

Terminology about computation and Finite algebra

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows ...
Emil Jeřábek's user avatar
7 votes

Does an initial algebra for a class have to belong to the class itself?

Yes, the initial algebra is by definition one of the members of the class for which it is initial. You may however be interested in the category-theoretic concept of a limit. Given a diagram (a ...
Andrej Bauer's user avatar
  • 29.1k
7 votes

Applications of algebraic geometry in type theory/programming language theory

This might not be exactly what you're looking for, but one application of algebraic geometry in programming languages is the analysis of linear loops: A linear loop is a very simple program of the ...
Shaull's user avatar
  • 5,646
7 votes
Accepted

Kleene Algebra for star-free regular expressions

You might be interested in bounded synchronization delay expressions. See [1] for details on these expressions. To sum up, they are equivalent to star-free expressions, but instead of using complement,...
Denis's user avatar
  • 8,893
6 votes
Accepted

Turing Machines as Coalgebras

Pavlovic et al. view Turing machines over a binary alphabet as coalgebras for the functor $\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$. The symbols $\lhd$ and ...
Henning Basold's user avatar
6 votes

Commutative operation benefits

One example where commutativity helps is in computing the determinant. Nisan showed that any non-commutative algebraic formula that computes the $n \times n$ determinant must have size $2^{\Omega(n)}$....
Robert Andrews's user avatar
5 votes

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

My intuition is that an NP-complete language of this type would cause a collapse of the polynomial hierarchy much like the one in the Karp–Lipton theorem. More specifically, if you go up to the ...
David Eppstein's user avatar
5 votes

Algebra oriented branch of theoretical computer science

Here are a lot of interesting answer, but nobody mentioned that every language $L \subseteq X^{\ast}$ is naturally associated with a monoid structure via the Nerode-Myhill congruence relation. The ...
StefanH's user avatar
  • 2,077
5 votes
Accepted

Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

Yes, these monoids have received attention in the research literature and actually lead to difficult questions. Definition. A monoid $N$ is called projective if the following property holds: if $f:N \...
J.-E. Pin's user avatar
  • 4,831
5 votes

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/...
Max New's user avatar
  • 1,695
5 votes
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$ ...
A.2's user avatar
  • 397
4 votes
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 ...
Bjørn Kjos-Hanssen's user avatar
4 votes

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 ...
J.-E. Pin's user avatar
  • 4,831
4 votes

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
Naysh's user avatar
  • 686
3 votes
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 ...
D.W.'s user avatar
  • 12.1k
3 votes
Accepted

Is the relation decidable?

Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases.
Bjørn Kjos-Hanssen's user avatar
3 votes
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 ...
user66277's user avatar
  • 131
2 votes

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, ...
xrq's user avatar
  • 1,175
2 votes

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 ...
Slimane Oulad-Naoui's user avatar
2 votes

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 ...
Thomas Ahle's user avatar
2 votes

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$. ...
A. D.'s user avatar
  • 161

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