Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algebra]

The tag has no usage guidance.

9
votes
0answers
74 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 ...
7
votes
0answers
52 views

Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem: Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
1
vote
0answers
52 views

Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part

Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
3
votes
3answers
100 views

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
9
votes
1answer
119 views

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

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
2
votes
1answer
64 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$ ...
4
votes
1answer
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 [1], there is an equivalence between order-sorted and ...
4
votes
1answer
253 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 ...
3
votes
1answer
104 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 ...
5
votes
1answer
225 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$...
2
votes
0answers
82 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 ...
0
votes
1answer
95 views

Is the relation decidable?

Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?
10
votes
0answers
269 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 ...
8
votes
2answers
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 ...
2
votes
0answers
64 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 ...
15
votes
2answers
670 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 ...
2
votes
1answer
90 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 ...
4
votes
1answer
121 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 ...
3
votes
0answers
73 views

Finding degree two subfield

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}]...
6
votes
1answer
221 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 ...
6
votes
0answers
108 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....
14
votes
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 ...
1
vote
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 ...
1
vote
1answer
69 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.
5
votes
0answers
70 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 ...
1
vote
0answers
113 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 ...
4
votes
1answer
258 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 ...
5
votes
1answer
178 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 ...
1
vote
0answers
55 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 ...
10
votes
2answers
448 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 ...
12
votes
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 ...
4
votes
1answer
133 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$? ...
32
votes
12answers
4k 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 ...
2
votes
1answer
162 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 ...
1
vote
1answer
103 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.
1
vote
0answers
38 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 ...
1
vote
0answers
86 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$...
0
votes
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 ...
1
vote
0answers
115 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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
0answers
134 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 ...
0
votes
1answer
231 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 ...
6
votes
1answer
138 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 ...
4
votes
1answer
199 views

The polynomial languages and ordered syntactic monoids

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 ...
5
votes
1answer
171 views

Why is it difficult to develop a subexponential functoral approach to discrete log

Call a discrete logarithm algorithm functoral if the commutative algebraic object that the algorithm acts on can be changed with another commutative object in the same category and the algorithm does ...
8
votes
1answer
253 views

Factoring low-degree polynomials

What is the fastest algorithm known for factoring polynomials with $n$ variables and total degree $\leq d$? Here, $n$ is growing and $d$ is fixed. Most work seem to consider the case when $d$ is ...
7
votes
1answer
396 views

Complexity of convolution in the max/plus ring

We can do convolution in $O(nlgn)$ for plus/multiply polynomials with fft. However the approach doesn't seem very generalisable to rings in general. Has there been any progress over the naive $O(n^2)...
1
vote
1answer
100 views

Is there a 'process algebra' to describe ACID transactions on a database?

There appears to be this beautiful algebra to help you think through the implications of Communicating Sequential Processes by Hoare. What I'm wondering, is there an equivalent algebra that helps ...
4
votes
0answers
82 views

Residual for transitive hull

I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...