Skip to main content

Questions tagged [algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
40 views

Maximum number of regions in partition induced by convex $k$-vertex polygons

I have a set $\mathcal{P}$ of $n$ convex $k$-gons (convex $k$-vertex polygons) on the (Euclidean) plane. These define a partition of the plane, or rather the plane sans the pointer on the contour of ...
einpoklum's user avatar
  • 995
1 vote
1 answer
61 views

How to create a 'hashing' function that maps up to 1 to N numbers uniquely to numbers 1 to N

I would like to use or create a hashing algorithm that takes K inputs from 1 to N and maps them uniquely to different numbers on 1 to N. K can be 1 to N. Ideally I would like the hashing alg to be ...
Drew's user avatar
  • 11
5 votes
1 answer
453 views

Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?

I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N. Afaik the Chomsky-Schützenberger representation ...
Crea Teeth's user avatar
1 vote
0 answers
63 views

Is NP a subring of the 2-adic integers?

Let me take the set $A = \{1, 2\}$ as the alphabet. By the bijective binary numeral system, $A^*$ has one-to-one correspondence to the set of nonnegative integers $\mathbb{N}$. As such, each language $...
Dannyu NDos's user avatar
0 votes
2 answers
85 views

Polynomial representations of Boolean functions

The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x_1x_2\cdots x_n$. I have a few questions: Is there a similar polynomial for the PARITY boolean function? Is there a ...
user avatar
0 votes
0 answers
38 views

Fastest Algorithm for Inverse of Positive-Definite Hermitian Toeplitz Matrix?

The Trench algorithm (1996) has complexity N*N to invert an N by N positive-definite Hermitian Toeplitz matrix. More recently (2005), Martinsson et al "A Fast Algorithm for the Inversion of ...
Mark's user avatar
  • 1
0 votes
0 answers
43 views

Algebra of error models and error correcting codes?

In coding theory we typically consider the situation where we have a channel that connects a sender and receiver. The messages flowing from the sender to the receiver are corrupted by an error source ...
Martin Berger's user avatar
2 votes
0 answers
39 views

Alternative parameterizations of the circle

When solving numerical problems with circles, one often has to sample these at numerous points, not necessarily in a uniform way. Evaluating the $(\cos\theta,\sin\theta)$ values can represent a ...
user avatar
1 vote
0 answers
33 views

matching vector families that form a group

Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)? You can find the definition of MV families here: https://homes....
Ali Gholami's user avatar
1 vote
1 answer
29 views

Number of binary words that form a group of Hamming weight at most d

Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?...
Ali Gholami's user avatar
0 votes
0 answers
37 views

Interpretation of semantics of queue algebra

I am trying to understand the semantics for stack algebra and queue algebra as introduced in section 8.5, "Specification Algebras" of textbook Software Engineering 1, Abstraction and ...
Avv's user avatar
  • 505
1 vote
0 answers
49 views

Parse algebraic expression into a list of operations

Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as: ...
Vladyslav Shlianin's user avatar
2 votes
1 answer
95 views

Not understanding step in Karger Algorithm: How to simplify a long product

I'm reading a book on Randomized Algorithms by Raghawan and Motwani and I don't understand the algebra/calculus of a step in the analysis of Karger's algorithm(Randomized min-cut). They have the ...
DenLilleMand's user avatar
2 votes
1 answer
126 views

How can I prove that the empty string is the identity element with regards to the operation of concatenation?

Let $w$ be a string over an alphabet $\Sigma$. It is obvious that $w \circ \epsilon = \epsilon \circ w = w$. However I'm having a hard time coming up with a proof for that (which I assume should be ...
NilsK's user avatar
  • 123
2 votes
0 answers
32 views

Algebraic structure of $(\text{Apply}, \{f: [T \to T]\})$? (is that even correct?)

Context In a program I am writing, the user is allowed to define user-defined functions in a file. These functions have the particularity that must be of type ...
Adrian's user avatar
  • 121
0 votes
0 answers
43 views

Lambda Calculus: Re-Ordering Arguments

Given any multivariable expression in Lambda Calculus (LC), e.g. for an arbitrary LC expression "op" for some non-commutative operation: ...
CorvinoDiNevarca's user avatar
2 votes
1 answer
175 views

Algorithm to construct a parabola that hits a given target and avoids given boundaries

I'm working on a video game and I'm struggling with the math behind one of the enemies. The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at ...
Andrew Clemens's user avatar
2 votes
0 answers
24 views

What's an efficient algorithm to check if a binary operator is residuated?

Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in ...
got trolled too much this week's user avatar
2 votes
1 answer
55 views

On the definition of Error-Correcting Codes

Let us start with the following well-known definition: Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is $\boldsymbol t$...
Chris's user avatar
  • 123
2 votes
1 answer
94 views

Meaning of Free (Arbitrary Abstract Algebra Term)

I'm currently learning abstract algebra and the word free appears (free monoid, free vector space) throughout different literatures. Is there a general (and simple) definition of the word (and ...
thoughtpolice's user avatar
0 votes
1 answer
109 views

"Term Rewriting and All That" - Exercise 3.10

I am studying Term Rewriting by reading Baader/Nipkow's book "Term Rewriting and All That". I am in chapter 3 - Universal Algebra, in the section 3.2 - Algebras, homomorphism and congruences....
Gabriel F. Silva's user avatar
2 votes
0 answers
73 views

The word "algebra" in category theory

I am currently learning category theory and a saying that I see a lot is that X is the algebra of something (e.g. Monoid is an algebra of something). Can someone explain to me what that means? Thanks!
thoughtpolice's user avatar
1 vote
2 answers
390 views

Complexity of simulating idle games (pt1)

An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical ...
Zachary Vance's user avatar
4 votes
0 answers
289 views

Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?

There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
Patrick Browne's user avatar
1 vote
0 answers
62 views

Abstract algebra algorithms

Let’s make a big list of algorithms relying on abstract algebra. This will help us see how ubiquitous algebra is in algorithm design. I’ll start with two: one is the General Number Field Sieve, the ...
Zirui Wang's user avatar
2 votes
0 answers
47 views

How to transform robot motor steps into X/Y coordinates?

I have a robot with two motors A and B connected to wheels 21.6mm in diameter. The motors move in steps, and there are twenty steps for each complete revolution of the wheel. To make the robot move ...
Mario Gianota's user avatar
1 vote
2 answers
73 views

Algebra for min/max bounds

I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, ...
Felipe's user avatar
  • 131
3 votes
1 answer
25 views

Algorithm to find the size of a quotient of a free group

Are there any algorithms to find the size of an algebraic quotient of a free group? It would take the generators as input and output the size. For example, an input could be something like {a,b: a^8=...
Alex Li's user avatar
  • 143
4 votes
0 answers
30 views

Testing whether polynomial is in algebra of other polynomials

A collection $\Sigma$ of polynomials is an algebra if: (1) $\lambda f + \eta g \in \Sigma$ for any $f,g \in \Sigma, \lambda,\eta \in \mathbb{R}$ and (2) $f,g \in \Sigma$ implies $fg \in \Sigma$. We ...
user avatar
2 votes
1 answer
71 views

totally ordered semigroups

Given a semigroup is it possible to give a total order to it? If not possible in the general case then what about the case of finitely generated finite semigroups? Does there exist a natural ...
Baby_Faced_Assassin's user avatar
0 votes
0 answers
137 views

Why algebraic semantics of programming languages have died out and have not used today?

Algebraic semantics is one type of semantics that uses algebraic expressions for connecting the formal descriptions of initial and final states of some operation of some operation that is defined in ...
TomR's user avatar
  • 1,401
4 votes
1 answer
113 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
JackSprat's user avatar
1 vote
2 answers
3k views

Dominance Law in Boolean Algebra

The dominance law states that x + 1 = 1 If we go by that logic, does that mean that x' + 1 = 1? Please just tell me if it's a yes(as I think that this is the answer but I just want to clear my ...
Bao Hsu's user avatar
  • 13
0 votes
1 answer
74 views

Boolean Algebra Simplifying complex equation

I am trying to simplify the following equation and I am getting stuck on a line and I can't cut it down any further. I'm not sure if certain 'moves' are legal or not. F(A,B,C,D) = A'B'C' +ACD + A’BCD ...
Shinji-san's user avatar
2 votes
2 answers
158 views

How to Apply Elementary Axioms from Kleene Star to an Inequality

Axioms For * \begin{align} 1 + aa^* &\leq a^* \\ 1 + a^*a &\leq a^* \\ b + ax &\leq x \to a^*b \leq x \\ b + xa &\leq x \to ba^* \leq x \\ \end{align} Elementary Results \begin{...
grant2088's user avatar
6 votes
1 answer
140 views

What is the fastest algorithm to check whether input table is a group?

Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not. I need to verify the four axioms of a group. The identity I can find it by ...
sssa's user avatar
  • 424
3 votes
0 answers
63 views

A book introducing proof theory needed (many-sorted FOL, classical non-Gentzen calculus, satisfiability in partial algebras, induction)

We define a signature as a triple $$\Sigma\ =\ (S,F,\mathrm{type})$$ where $S$ is a set of sorts, $F$ a set of $n$-ary function symbols $f$ of the type $\mathrm{type}(f)$ $=$ $(M_1,\dotsc,M_n\...
user avatar
4 votes
1 answer
523 views

What is the difference between Boolean Algebra and Boolean Lattice?

What is the difference between Boolean Algebra and Boolean Lattice? I have already searched on Google but could not find a reasonable answer?
Kishan Kumar's user avatar
1 vote
1 answer
61 views

What's the theory behind the operator precedences of common operators?

Could for example the precedence ordering of addition, multiplication, exponentiation, boolean and/or and zip/cross product be inferred from a few rules?
Johannes Riecken's user avatar
2 votes
0 answers
95 views

Optimal vector decomposition

I have a vector $v \in \mathbb{N}^k$ and a set of vectors $R \subset \mathbb{N}^k$, with $k \ll \left\vert R \right\vert $. I would like to find a way to obtain all the possible bases of $\mathbb{N}^...
Michele Ippolito's user avatar
24 votes
2 answers
923 views

Is there a non-trivial type which is equal to its own derivative?

An article called The Derivative of a Regular Type is its Type of One-Hole Contexts shows that the "zipper" of a type—its one hole contexts—follow the differentiation rules in type algebra. We have: ...
Matthew Piziak's user avatar
1 vote
1 answer
81 views

Isomorphism of finite dimensional polynomial algebras over finite fields

For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between: $$\frac{\mathbb{F}_q[x]}{\...
MathManiac's user avatar
1 vote
0 answers
24 views

Is there evidence to suggest Macsyma was directed at the Diophantine equations in the Entscheidungsproblem?

I'm reading the book The Annotated Turing by Charles Petzold. In it he mentions the Diophantine equations - which was a joy to read. This then lead to Hilbert's 10th problem - finding an algorithm ...
hawkeye's user avatar
  • 1,199
8 votes
1 answer
31k views

Convert HSV to RGB colors

HSV colors are composed of a triple of numbers: hue $\in [0, 360)$ (in degrees), saturation $\in [0, 1]$ and value or brightness $\in [0, 1]$. RGB colors instead are more well-known and are also ...
user avatar
8 votes
2 answers
558 views

Solving systems of linear equations over semirings

So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm ...
Jake's user avatar
  • 3,800
1 vote
1 answer
37 views

Producing an algebric equation from a graph

I'm writing a computer game and one of my game's objects must follow a movement path that is very similar to the following graph. The bold lines are the Y and X axis. In order to be able to code this ...
exophrenik's user avatar
5 votes
1 answer
92 views

Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$

(At the very bottom of this, I will shortly describe the motivation for this question.) Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ ...
G. Bach's user avatar
  • 2,019