Hot answers tagged

27 votes

Algebra oriented branch of theoretical computer science

There have been recent developments in dependent type theory which relate type systems to homotopy types. This is now a relatively small field, but there is a lot of exciting work being done right ...
user avatar
  • 13.2k
25 votes

Algebra oriented branch of theoretical computer science

Algebraic geometry is used heavily in algebraic complexity theory and in particular in geometric complexity theory. Representation theory is also crucial for the latter, but it's even more useful when ...
user avatar
18 votes
Accepted

List of number theoretic or algebraic problems in various complexity classes

Algebraic geometry Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is conjectured to be in $\mathsf{P}$ (and is ...
user avatar
15 votes

Algebra oriented branch of theoretical computer science

Your knowledge of field theory would be useful in cryptography, while category theory is heavily used in the research on programming languages and typing systems, both of which are closely related to ...
user avatar
12 votes

Is there a theory that combines category theory/abstract algebra and computational complexity?

[Computational complexity and category theory] seem like such natural pairs. Given the prominence of computational complexity as a research field, if they were such natural bedfellows, maybe somebody ...
user avatar
12 votes

Complexity of computing the order of a permutation group

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress. For reference, ...
user avatar
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-...
user avatar
11 votes

Algebra oriented branch of theoretical computer science

Field theory and algrebraic geometry would be useful in topics related to error correcting codes, both in the classical setting as well as in studying locally decodable codes and list decoding. I ...
user avatar
11 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 ...
user avatar
  • 7,653
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 ...
user avatar
11 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 ...
user avatar
  • 4,721
11 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 ...
user avatar
  • 16.6k
11 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, ...
user avatar
10 votes
Accepted

Complexity of computing the order of a permutation group

As a complement to Joshua Grochow's answer: Computing the order of a permutation group given generators is in P by Schreier–Sims algorithm, see also p. 8-9 of these lectures notes by Luks. Just as ...
user avatar
9 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 ...
user avatar
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 ...
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 ...
user avatar
  • 4,721
7 votes

Algebra oriented branch of theoretical computer science

There are some problems in computational learning theory, machine learning and computer vision that can be solved using commutative algebra and algebraic geometry. For instance, convergence of the ...
user avatar
7 votes

Computability of infinite-dimensional vector space

Short answer The general answer is that computability is easy for locally compact spaces, doable for separable spaces, and hard for non-separable spaces. The short anwer for a particular example, ...
user avatar
  • 26.7k
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 ...
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 ...
user avatar
  • 26.7k
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,...
user avatar
  • 7,653
6 votes

Gröbner bases in TCS?

Grobner bases are used for the fastest list decoding algorithms for Reed-Solomon codes: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&rep=rep1&type=pdf
user avatar
6 votes

Algebra oriented branch of theoretical computer science

Have you thought about looking at computer algebra? Axiom is a computer algebra system where the type system is modelled after Category Theory (or Universal Algebra, depending on your view). There are ...
user avatar
6 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 ...
user avatar
  • 10.5k
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 ...
user avatar
6 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 ...
user avatar
  • 5,261
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)}$....
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 ...
user avatar
  • 1,947
5 votes

What is necessary and/or sufficient requirement for a subring of a field to be computable?

The question of how to find computable substructures of algebraic structures was studied by Jens Blanck and myself in the paper "Canonical Effective Subalgebras of Classical Algebras as Constructive ...
user avatar
  • 26.7k

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