Questions tagged [algebra]

The tag has no usage guidance.

17 questions
29 views

Confusion regarding algebraic specification of the queue

I was given the following question in the test where I had to write the algebraic specification and its axioms based on below-defined operations: ...
64 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:...
59 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 ...
38 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 ...
48 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{...
66 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 ...
53 views

672 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: ...
58 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]}{\...
17 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 ...
8k 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 ...
203 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 ...
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$ ...