Questions tagged [algebra]
The algebra tag has no usage guidance.
96
questions
2
votes
1
answer
114
views
Complexity of finding approximate solutions for systems of polynomial equations
Consider the following problem:
Input: $(p_1,...,p_n, \epsilon)$ where each $p_i$ is a polynomial in $m$ variables with integer coefficients and $\epsilon>0$.
Output: If there is $(r_1,...,r_m) \in ...
- 23
5
votes
0
answers
201
views
Satisfiability and a Galois Theory Analog
Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows:
$$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$
where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
5
votes
1
answer
129
views
Commutative operation benefits
With an associative operation I can rewrite a computation tree
+
/ \
+ 4
/ \
+ 3
/ \
+ 2
/ \
0 1
to be more efficient ...
- 71
5
votes
2
answers
191
views
Reference request: An algebraic characterisation of LTL[XF]-definable word languages
I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1).
A similar ...
- 1,110
7
votes
1
answer
301
views
Kleene Algebra for star-free regular expressions
TLDR: Is there a notion of Kleene Algebra for star-free regular expressions?
Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent ...
- 193
2
votes
0
answers
76
views
Relation between automorphism group of a linear code and its dual code
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.
In ...
- 387
7
votes
1
answer
344
views
Technical lemma about curves used in original proof of PCP theorem
I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn'...
- 153
7
votes
2
answers
636
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 ...
- 515
10
votes
2
answers
790
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, ...
- 1,125
9
votes
1
answer
363
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 ...
- 163
1
vote
0
answers
22
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 ...
- 12.5k
11
votes
0
answers
146
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 ...
- 361
7
votes
0
answers
57
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,...
- 71
1
vote
0
answers
63
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\}$ ...
- 1,947
3
votes
3
answers
143
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 ...
- 1,947
9
votes
1
answer
191
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 $...
- 1,947
2
votes
1
answer
72
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$ ...
user49685
3
votes
1
answer
59
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 ...
user37129
4
votes
1
answer
362
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 ...
- 822
3
votes
1
answer
157
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 ...
- 1,122
5
votes
1
answer
234
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$...
- 992
2
votes
0
answers
117
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 ...
- 1,537
0
votes
1
answer
145
views
Is the relation decidable?
Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?
- 1,009
9
votes
0
answers
299
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 ...
- 822
8
votes
2
answers
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 ...
- 263
2
votes
0
answers
70
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 ...
user44741
14
votes
2
answers
732
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 ...
- 1,552
2
votes
1
answer
96
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 ...
- 1,537
4
votes
1
answer
147
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 ...
- 389
3
votes
0
answers
82
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}]...
- 243
10
votes
1
answer
454
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 ...
5
votes
0
answers
111
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....
- 383
14
votes
3
answers
2k
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,947
1
vote
0
answers
89
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,537
1
vote
1
answer
88
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.
- 574
5
votes
0
answers
76
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,537
1
vote
0
answers
116
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 ...
- 111
6
votes
1
answer
359
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 ...
- 753
5
votes
1
answer
218
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 ...
- 5,261
1
vote
0
answers
65
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 ...
- 383
10
votes
2
answers
608
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 ...
- 10k
12
votes
2
answers
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 ...
- 12.5k
4
votes
1
answer
140
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$?
...
- 11k
33
votes
12
answers
6k
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 ...
- 471
3
votes
1
answer
251
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 ...
- 39
1
vote
1
answer
113
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.
- 11
1
vote
0
answers
43
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 ...
- 383
1
vote
0
answers
91
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$...
- 1,292
0
votes
1
answer
201
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,292
1
vote
0
answers
122
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 ...
- 1,292