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, ...
- 32.4k
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 ...
- 4,771
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 ...
- 16.7k
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-...
- 36.9k
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 ...
- 8,598
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 ...
- 3,946
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 ...
- 6,967
8
votes
Uses of algebraic structures in theoretical computer science
Algebra (and algebraic geometry) has had a pretty big role to play in cryptography, with elliptic curve groups, (number-theoretic) lattices, and of course $\mathbb{Z}_p$ being the basis for nearly all ...
- 109
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 ...
- 4,771
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 ...
- 11.7k
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 ...
- 28.3k
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 ...
- 16.9k
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 ...
- 5,531
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,...
- 8,598
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 ...
- 326
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)}$....
- 743
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 \...
- 4,771
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 ...
- 50.9k
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 ...
- 2,037
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/...
- 1,653
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$ ...
- 397
4
votes
Accepted
Algebra and algebraic data types
In my understanding, algebraic data types are basically types whose terms arise as the terms freely constructed by an algebraic specification: the operations of this specification being the term-...
- 454
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 ...
- 4,475
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 ...
- 4,771
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 ...
- 11.7k
3
votes
Accepted
Is the relation decidable?
Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases.
- 4,475
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 ...
- 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, ...
- 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 ...
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 ...
- 958
Only top scored, non community-wiki answers of a minimum length are eligible