# Questions tagged [algebra]

The tag has no usage guidance.

89 questions
Filter by
Sorted by
Tagged with
153 views

### What category are Tagless Final Algebras final In?

The Haskell and Scala community have been very enamored recently with what they call tagless final 'pattern' of programming. These are referenced as dual to initial free algebras, so I was wondering ...
300 views

### Applications of algebraic geometry in type theory/programming language theory

Lately, I have become interested in algebraic geometry and have started reading on it. I still know very little about this field, but I do want to know if it has any connection with my main field, ...
222 views

### Turing Machines as Coalgebras

I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
20 views

### Worst case polynomial in elimination theory under rank conditions?

Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
98 views

### Are there cascade decompositions of machines that are more general than finite automata?

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
56 views

67 views

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

In the context of algebraic data types, a concept of initial algebras is usually defined, e.g., in the following way: An algebra $S$ is initial in a class $C$ of algebras iff for every $A\in C$ ...
57 views

### Relation between OSAs and grammars

Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)? If I'm not mistaken, according to , there is an equivalence between order-sorted and ...
284 views

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

Because Bitcoin and many other cryptocurrency mining certificates are "rare" in that their respective hash is less than a very small number, can we leverage their rarity in probabilistic proofs of ...
120 views

### Connection between algebraic logic and computational complexity of logics?

I'm learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a given logic might help the study of the logic itself from a computational point of view. In ...
227 views

### Terminology about computation and Finite algebra

I am looking for the name of something that may have one. A finite algebra $\mathcal{A} = (E, \{f_1, f_2, \ldots, f_k\})$ is a non-empty set $E$ together with some functions $f_i$ from $E^{r_i} \to E$...
102 views

### On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits

As I understand from the survey "Progress on Polynomial Identity Testing - II" a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown. However, there exists paper ...
124 views

### Is the relation decidable?

Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?
284 views

### What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?

$\mathsf{GNI}$ Private Coin In [GMW85], the authors provided the famous interactive proof $\mathsf{IP}$ of Graph Non Isomorphism $\mathsf{GNI}$. The $\mathsf{GNI}$ protocol entails a verifier ...
1k views

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

I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ concepts corresponds to. Basically, C++ concepts allow to define ...
66 views

### Standard basis for recurrence relations

In polynomial algebra there is a powerful tool for treating system of polynomial equations. It is standard or Groebner Bases. It allows to verify if system is consistent, eliminate variables, reduce ...
683 views

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

Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
91 views

### the number of rational points of a curve modulo 2

Consider the language $L=\{f, q\}$ - the number of solutions of equations $f(x,y)=0$ in $\mathbb{F}_q^2$ is equal to zero modulo $2$, where $q = 2^m$. Does $L$ belong to $P$? to $NP$? ($f$ is written ...
135 views

### What automorphisms on a Markov Chain imply a uniform limiting distribution?

Consider an irreducible aperiodic Markov chain $M$, modeled as a connected directed graph with weighted edges. The existence of certain (graph) automorphisms on this Markov chain imply various ...
75 views

Let $K=\frac{\mathbb{Q}[x]}{<f(x)>}$ where $f(x)$ is irreducible over $\mathbb{Q}$ and has even degree. I want to find $K_2$ such that $\mathbb{Q} \subseteq K_2\subseteq K$ and $[K_2:\mathbb{Q}]... 1answer 260 views ### Chomsky Schützenberger enumeration theorem In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is$\mathbb N$-algebraic, if the grammar is unambigious. In some ... 0answers 109 views ### Algebraic dependence of roots of irreducibles over a finite field I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math.... 3answers 1k views ### On the realisation of monoids as syntactic monoids of languages Let$L \subseteq X^{\ast}$be some language, then we define the syntactic congruence as $$u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L$$ and the quotient ... 0answers 88 views ### Counting points on curves It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of$\mathbb{F}_q$-rational points on a ... 1answer 71 views ### What's the relationship between “free theorems” and “free objects” What's the relationship between free theorems and free objects from algebra. They seem quite similar. I'm wondering if there's an underlying principle here. 0answers 71 views ### Finding of dimension of algebraic varieties I have found that the problem of finding of dimension of algebraic varieties over$\mathbb{C}$is$NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf). Are ... 0answers 115 views ### Computing$a^e \mod p^n$Efficiently It is well known that we can compute: $$a^e \mod m$$ in$O(\log e \log ^2 m)$bit operations (assuming multiplication$nm$in$O(\log n \log m)$time) via exponentiation by squaring. I am wondering ... 1answer 325 views ### Algebra and algebraic data types Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)? Presumably a free monoid can be considered to be isomorphic to the ... 1answer 185 views ### Is algebraic dependency decidable? A set of numbers$S=\{x_1,...,x_n\}$is said to be algebraically dependent if there exists a (multivariate) polynomial$p$with coefficients in$\mathbb Q$whose roots contain$x_1,...,x_n$(or a ... 0answers 62 views ### The curve used in Parvaresh-Vardy decoding Consider the Parvaresh-Vardy list decoder. As I understand it, the idea is to decide on a curve over an extension field of the form$(f,f^h mod E, f^{h^2} mod E,\dots)$and then evaluate each of ... 2answers 469 views ### Complexity of computing the order of a permutation group Given two permutations$g$and$h$over$n$elements (i.e., members of$S_n$), what is the complexity of computing the order of the subgroup generated by$g,h$? Or just of deciding whether the ... 2answers 1k views ### List of number theoretic or algebraic problems in various complexity classes I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example, GCD in$NC^1$is open, factoring in$P$is open, computing sheaf ... 1answer 137 views ### Solving a system of sums-of-powers polynomials What is the complexity of calculating the values of the integers$x_i$, where$0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values$s_m = \sum_{i=1}^k x_i^m$? for$1 \leq m \leq k$? ... 12answers 5k views ### Algebra oriented branch of theoretical computer science I have a very strong base in algebra, namely commutative algebra, homological algebra, field theory, category theory, and I am currently learning algebraic geometry. I am a math major with an ... 1answer 171 views ### Computability of infinite-dimensional vector space So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be ... 1answer 104 views ### What is necessary and/or sufficient requirement for a subring of a field to be computable? [closed] As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring? Conditions on either field or subring are fine. 0answers 40 views ### Decoding of Gabidulin codes Consider the space of matrices in$\mathbb{F}_q^{n \times m}$where$\mathbb{F}_q$is the finite field with$q$elements. We can define a metric on this space, given by$d(A,B) := rank(A-B)$, called ... 0answers 89 views ### Restoring symmetry in certain combinatorial bijections? I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair$\cal{F} = (F,f)$where$F$is an$n$... 1answer 194 views ### Classifying noetherian simple groups by order type? A (possibly infinite) group$G$is noetherian if it satisfies the following equivalent conditions: (1) every subgroup of$G$is finitely generated, (2) there is no infinite strict ascending chain of ... 0answers 116 views ### Spectrum of a variety: a possible connection btw ordinals and structures? Consider a variety of algebras$\mathbb{V} = \mathbb{V}(\sigma,\tau)$which consists of the set of algebras defined over a fixed signature$\sigma$and satisfying a set of identities$\tau$. We may ... 0answers 113 views ### Possible generalizations of associativity? The well-known notion of associativity in algebra leads to structures with interesting properties, such as groups or semigroups. According to a paper by John Rhodes, some researchers in algebra and ... 0answers 73 views ### Composition series and isogeny I'm not sure this question is appropriate for this site, but it might have some connections with computational algebra. Consider a fixed "category"$\sf{Cat}$(in the sense of category theory, but ... 0answers 136 views ### Extending the notion of independence Background I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered here but I couldn't find a satisfactory ... 1answer 234 views ### Extending semigroup theory? In an earlier question I proposed a definition of associativity for ternary relations generalizing the usual notion for composition laws. I'm still not sure whether this definition makes sense, but if ... 1answer 146 views ### Where does randomness help when deciding algebraic geometry over$\mathbb{C}\$?

If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether ...
A polynomial language is a languge which could be represented as the finite union of languages of the form: $$A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X$$ Such an ...