Mathematics - 2017-03-05 (page 2 of 4)

Fruitful Approach

12:14 PM

The culmination of my work: math.stackexchange.com/questions/2172809/…

on smallest grammar algorithms

unfortunately, still seems P != NP ._.

H @Astyx

Hi

Astyx

Hi

Fruitful Approach

See my post

Smallest grammar problem is open and easily stated

Sort of like twin primes or Fermat

Astyx

Don't have time right now

Fruitful Approach

But FREAKIN IMPOSSIBLE to solve

alan2here

putting binary trees in variables, comparing them for equality, performing operations with them like one between two binary trees that yeilds a thrid, and algebraically rearranging formuli where all the variables are different binary trees

is this a thing in maths? we have this sort of thing with sets, graphs, vectors etc...

Astyx

12:22 PM

I believe it is

alan2here

rooted multiplication seems to work well with them, being something to do with graphs but seems to work fine on trees too

((), ()) * (((), ()), ()) = ((((), ()), ()), (((), ()), ())) with rooted

cool, whats it called @Astyx ?

Astyx

I'm not sure what you're asking for

But binary trees are just specific cases of graphs

alan2here

yes, and as so have different properties, for example cartesian multiplication of binary trees shaped graphs always yeilds a non-tree shaped graph.

DHMO

@Astyx bonjour

Astyx

Hi @DHMO

DHMO

12:27 PM

comprends-tu si j'ecrire comme "parskjlveu"?

Astyx

Absolument pas

alan2here

If I asked for algebra that was closed over prime numbers for example, it wouldn't include division.

DHMO

hein?

@Astyx ca veut dire "parce que je le veux"

alan2here

ahh, "closed over", helpful term :)

Fruitful Approach

What group is this? {1, A, B, AA, AB, BA, BB, AAA}?

DHMO

12:29 PM

@alan2here we say prime number is closed under xx operation

Astyx

@DHMO C'est très incorrect

DHMO

@FruitfulApproach length-2 strings with AAA

Fruitful Approach

?

No, group

DHMO

@Astyx well in english u also hv abbreviations lik dis

Fruitful Approach

What group can it be viewed as?

DHMO

12:30 PM

no idea @FruitfulApproach

Astyx

But they're still wrong and should be avoided @DHMO

@Fruitful you need an operation to define a group

DHMO

@Astyx cela depend sur ton age :p

Fruitful Approach

Yes, I do have one, it's defined via its definition as a group action

1

Q: A group action associated with a smallest grammar algorithm. Ways to reduce size?

See these two posts for a background: Smallest grammar algorithm recursion Smallest grammar algorithm group action Here is some output of code I've written in python. Ask if you want to run it. This output is generated by input $s = abc\cdot abc \cdot abc$. # generators = 6: [A -> cab, B ->...

By its activity on a string

Astyx

@alan2here I'm still not sure what you're looking for

Fruitful Approach

It is not the best way to define a group, but it's what I'm working with

Astyx

12:32 PM

@DHMO I'm against deterioration of language, if that's what you're asking :p

DHMO

@Astyx cela s'appelle evolution

Astyx

@Fruitful could you explain what the operation is ?

Fruitful Approach

It's in the post

But

Astyx

Where ?

DHMO

@Astyx une moitie des lettres en "tiennent" est redundant

Fruitful Approach

12:33 PM

A -> abc is a grammar rule, right?

Act on the string s = abcabc

by taking the first (leftmost) abc and converting to A

so As = A abc

group actions

A^2 s = AA

alan2here

@DHMO I've made up various operations that binary trees are closed over, and some of thease are commutative and associative with themselves, and so follow algebraic rules, I guess they are all analogous to multiplication, and three of them can together be used to construct every binary tree from the trivial tree ((), ()).

Fruitful Approach

A^3 s = s, so we say A^3 = id artificially

Astyx

@DHMO Je ne vois pas pourquoi la redondance est un problème

Fruitful Approach

It's sort of like how the Dihedral group is defined to be symmetries of a shape, but way different too

DHMO

@Astyx et ainsi je vois pas comment abbreviation est un probleme

Fruitful Approach

12:36 PM

Oh yeah, we artificially say A(A^2 s) has nothing to do, except restart, for the sake of forming a group

Astyx

@DHMO Parce que je n'ai pas compris ce que tu voulais me dire précédemment, par exemple

Fruitful Approach

If we said $A \circ (s = AA)$ does nothing, we don't have a group

DHMO

@Astyx d'accord

Fruitful Approach

So we say $A$ acting 3 times on $s$ goes back to $id \circ s = s$

Astyx

@Fruitful What's $ss$ for instance ?

Little Rookie

12:37 PM

Hello chat, anyone knows of reference material/textbook for ordinary differential equation that has interesting(not basic) exercises?

Fruitful Approach

Kinda cheap, but least I got a group in there!

would you multiply two polygons when talking about Dihedral groups?

$s$ is an object

Astyx

Oh right ...

Fruitful Approach

a certain subset of grammars of $s$ is what is being acted on

What certain subset is just what happens to be out of leftmost grammar rule actions

alan2here

@LittleRookie Tried Khan Academy?

Fruitful Approach

I strongly believe that there is always a "leftmost" smallest grammar, just need to prove that in a lemma some time

DHMO

12:40 PM

@Astyx trouve l'adherence de {1} dans la topologie sur R qui exclut 0, c'est-a-dire qu'un ensemble est ouvert s'il ne contient pas 0

Astyx

And what is B ?

DHMO

ou s'il est R

Fruitful Approach

$B$ is a variable, the left side of a grammar rule, a string symbol, all depends on context

In my post, we let $B$ denote the group element as well

Astyx

Can't right now @DHMO

DHMO

d'accord

Fruitful Approach

12:41 PM

The idea is to enumerate all fully expanded smallest grammars (up to pure literal rule), and recursively apply the algorithm to get down to the actual smallest grammars

Astyx

So in itself $A$ is a function on a language

And you claim composition is a group law for the set of such functions

Fruitful Approach

For instance $S \to AAA, A \to BB, B \to aaa$ fully expanded up to literals would bve $S \to BB \cdot BB \cdot BB$.

Astyx

Am I right ?

Fruitful Approach

You might be able to pull that off, but I'm humble so I stick with a single string

Oh yes, you're right

the language is the certain subset of starting rules for grammars of $s$

Astyx

And why is $A^3$ the identity ?

Fruitful Approach

12:44 PM

The idea is then that a smallest grammar of $s$ is found by recursively then (after you find $S \to B^6$ applying the smallest grammar on it.

the smallest grammar algorithm on *it

Every smallest grammar algorithm has to start with the input $s$

So $A^2$ fully takes all occurences of $abc$ out

if we defined $A^3 s = A^2 s = $ "$AA$", we don't have a group, and so no fanciness

Astyx

So you convieniently say that $A^3 = id$ so that you have an identity element and an inverse

Fruitful Approach

Yep

All out of convenience

Little Rookie

@alan2here khan academy is useful for basic concepts. But im looking for not basic/easy exercises to prepare for a hard exam :(

Fruitful Approach

I've tried many other definitions, this is just the latest

I've tried positional occurences using indexes, using positions, etc

This one seems most natural

Astyx

What happens if we have, say $A \to abc$ and $B \to ca$ ?

Fruitful Approach

12:47 PM

You search for $abc$ left to right in the string (on a computer), and if it doesn't occur, that's easy to check for

That would never happen as we define the generating set to be irreducible (or compressibly repeating, irreducible) substrings of input $s$.

$ca \not\leqslant s$

It is associative as it maps a set to a set, not sure though, thanks for that!

Astyx

No you're right, my question was silly

Fruitful Approach

It should be hmmm..

Why is that obvious to you?

You've instilled doubt in me

Astyx

Well composition is always associative

I think

Fruitful Approach

I know that, but with the mess I have, it's hard to picture here

Astyx

Because if you have three functions (defined correctly) $((f\circ g)\circ h)(x) = f(g(h(x))) = (f\circ (g\circ h))(x)$

Fruitful Approach

12:52 PM

I guess because consuming substrings, as long as the order is kept, should result int the same thing

Astyx

So $(f\circ g)\circ h = f\circ (g\circ h)$

Fruitful Approach

Yes, but I didn't frame it as a set composition, though it has to be, I guess since it is (hopefully) a group action

Astyx

Ok so what is your question ?

Fruitful Approach

Question is how can I reduce the size of the action group

As it clearly seems to be unwieldy in size

Astyx

depends on the functions you have

Fruitful Approach

12:55 PM

I want $1 million dollars in the bank to by food for my family and hippies, invest in companies, projects, and support animal shelters

I'm trying to prove P=NP

lol

Astyx

Could you give an example of what you're trying to achieve ?

Fruitful Approach

I reason, most algorithms only take up a small amount of code on a machine. What about filling in the rest of code memory with some freakin crazy algorithm that is group theoretical, just like AKS primality test.

Yes

Let $s = aaa aaa aaa aaa$

Thats $a^12$

$a^{12}$

Now on paper find the smallest grammar, one should be: $S \to AA, A \to BBB, B \to aa$

Astyx

Why ?

Fruitful Approach

?

Why what

If you're asking why that's a smallest grammar, it's because I've worked with them so long that it's obvious. But with the above algorithm you could actually prove that it is one.

If you're asking why work on this problem, it's because it's interesting, and the fact that no one has tried many of the approaches I come up with. People seemed to have abandoned the problem, so I'm a lone shark attacking it like a bag of meatrix

Astyx

What do you mean by smallest grammar ?

Fruitful Approach

1:01 PM

Oh

Google it real fast

Astyx

I have

Fruitful Approach

Do you know what a context-free grammar is?

Grammars are important in formal language theory, applications include programming language, compression, etc.

But also, if I can show that there is a polynomial time algorithm for finding one, then an automatic corollary is that P = NP, and I will take the money, unlike Perelman

^_^

Astyx

Why isn't $A \to a^{12}$ a grammar ?

Fruitful Approach

It is one

it's just not smallest

One application: a smallest grammar for $a^n$ will give you the least number of multiplications required to compute that exponential say if you replace $a$ by a real number

Astyx

Oh I see

Fruitful Approach

1:05 PM

So you're limited to concatenation, not exponents. But what if!? If you could do this with a single operation, maybe you could extend the methods and do things like optimize over a ring

It sucks that no one studies smallest grammar any more: I'm the only person asking these questions on MSE

Astyx

I have to go now, I'll give this some thoughts

Fruitful Approach

K

Thx for your interest

Aww.. man. He didn't even upvote! Got burned, son!

LOL

I mean she

:D

Yes, I fish for upvotes

skullpetrol

Link please.

Fruitful Approach

Hard problems only hard because the symmetry involved is convoluted and undiscovered.

1

Q: A group action associated with a smallest grammar algorithm. Ways to reduce size?

See these two posts for a background: Smallest grammar algorithm recursion Smallest grammar algorithm group action Here is some output of code I've written in python. Ask if you want to run it. This output is generated by input $s = abc\cdot abc \cdot abc$. # generators = 6: [A -> cab, B ->...

abstract-algebra group-theory optimization formal-languages formal-grammar

Up vote

up vote!

YAYAYAYAYA!

\o /

Make it go up, pls :P

skullpetrol

:D

Fruitful Approach

1:13 PM

OMG

THANK YOU!!!!

skullpetrol

np

Fruitful Approach

That code took a while to debug, and I've put months of thought into the problem, and have tried many other approaches. This one seems most promising. I even tried game theory, but apparently Nash Equilibria are also hard to compute.

Any questions?

comments welcome, like "WTF you been smokin" would do

Dat wacko tocracco

I quit for 6 months, then sister in-law came round smokin up like a train. This will be my last pack, then going to quit for a year

Soon herb will be recreational in CA. But I will definitely do edibles, to save my lungs

Matti

Hey! A got a question: If a matrix A is such that A^7=A, what's A^2001? I found A^3 but I did several "iterations" with division algorithm with 7. Is there a shortcut I'm not seeing? :(

Fruitful Approach

Yes, it's the smallest grammar of A^2001, but good luck computing it!

Can {1, A, B, AA, AB, BA, BB, AAA} even be a group?

I'm having doubts

Nvm, I guess it's Z_6

Matti

1:28 PM

The smallest grammar? o_O

Fruitful Approach

3

Q: A group action associated with a smallest grammar algorithm. Ways to reduce size?

See these two posts for a background: Smallest grammar algorithm recursion Smallest grammar algorithm group action Here is some output of code I've written in python. Ask if you want to run it. This output is generated by input $s = abc\cdot abc \cdot abc$. # generators = 6: [A -> cab, B ->...

abstract-algebra group-theory optimization formal-languages formal-grammar

Matti

D:

Compulsive Mathurbator

Say I'm trying to find the number of onto(surjective) functions from the set $A=(1,2,3,...n)$ to the set $B=(1,2,3)$.

The total number of functions from A to B is $3^n$ as each element in a has three options to be mapped to.

Then I subtracted all possibilities where one of the elements of B is not mapped to, $3*2^n$ in number, as there are three choices of the skipped element of B and two each for all elements in A. But this double counts all cases where only one element of B is mapped to, of which there are three, so adding them gives me.

DHMO

@CompulsiveMathurbator i dont think so

Compulsive Mathurbator

@DHMO All right, thanks my aqueous friend.

DHMO

1:41 PM

@Matti prove that A^(6n+1) = A

Matti

@DHMO Yes! That's a shourtcut! :D How did you know I needed (6n+1)?

Semiclassical

Hi chat.

skill patrol

hi

Semiclassical

The observation is that if A^7=A, then A^6 acts on A like the identity matrix. @Matti

And while we can't conclude that A^6 actually equals 1 (A might be invertible) that still sets a very strong constraint on A^n.

Matti

1:57 PM

@Semiclassical Thanks so much for the insight! :)

skill patrol

feeling any better @BalarkaSen?

Balarka Sen

a lot

skill patrol

cool

Balarka Sen

but there's room for improvement yet

Alessandro Codenotti

for $X\vee Y$ to be independent up to homeomorphism of the points identified by the wedge sum is enough that $X$ and $Y$ are path connected, right?

Balarka Sen

2:06 PM

I think you mean $X \vee Y$, right?

Alessandro Codenotti

indeed

why is it called a wedge sum if the symbol used to represent it is not a wedge!

Balarka Sen

Hah. The \wedge is wedge in the context of differential forms, but smash product in the context of topology :)

Hmm, so, about your question. I don't think $X \vee Y$ need to be same even upto homotopy equivalence if you change around basepoints - even if $X$ and $Y$ are path connected.

I want to mumble something like two cones on Hawaiian earrings wedged at the bad points vs wedged at the cone points but I haven't checked anything

Yeah, I think that works actually. The former shouldn't be contractible.

Alessandro Codenotti

you're right

Balarka Sen

Great! I knew I saw it somewhere but couldn't find it.

On the other hand if $X$ and $Y$ are CW complexes they should definitely be homotopy equivalent.

mick

0

Q: Simplify $a x b + a' x b' + a'' x b'' $?

Let $a,a',a'',b,b',b'',x$ be square matrices with real entries. Notice matrix multiplication is not commutative , but matrix miltiplication behaves as a noncommutative ring. I know we can " slightly simplify " $ A X + X B $ to $( A + Q) X$ where $ Q X = X B $. ( or similar to the other side by ...

linear-algebra matrices computational-complexity

LHF i think

Balarka Sen

2:18 PM

@Alessandro The reason why $CH \vee CH$ is not contractible is that $\pi_1$ (based at bad point - also the wedge point) has nonzero elements. Look at the loop which first winds around all the circles clockwise in one $H$ and then winds around all the circles counterclockwise in the other $H$. There should not be any nullhomotopy of this.

I also believe that is from a MO post but I can't find it either :P

Alessandro Codenotti

that intuitively works, I have no idea how to properly justify it though

Balarka Sen

It should be a discontinuity argument. If you try to push the two loops towards their respective cone points (only way to nullhomotope) then that homotopy would get discontinuous near the bad point.

I'm not going to try to prove it though.

This problem goes away if you use reduced cones instead (X x [0, 1] mod X x 0 and p x [0, 1] for some basepoint p \in X)

user379685

2:34 PM

Hello, could someone help me find the partial derivatives for this function f(x,y)=x^2+y^2 if xy=0 and 1 if xy!=0

user379685

2:49 PM

Nevermind, got it.

Little Rookie

Hello all, if i'm given a general solution of a first order linear ODE and some vector fields, how should i determine which vector field belongs to the linear ODE?

One way is to derive the differential equation from the general solution. Then, we can use it to find the right direction field.

Is there any method without finding the differential equation?

Mats Granvik

Is mathematics more about counting the numbers or connecting the dots?

skill patrol

depends on what area

Mats Granvik

3:06 PM

@skillpatrol I had in mind the kind of exercise where you have numbers and dots spread out on a paper, and then when you connect the dots by counting the numbers in the right order it becomes a picture of some animal like the Easter bunny.

skill patrol

sounds like geometry

DHMO

@AlessandroCodenotti $\omega_1$ has no minimum but its order topology still has the property I mentioned yesterday, right?

Semiclassical

Googling "Easter bunny connect the dots" gives exactly that, albeit not on a grid

It's a common simple drawing puzzle since it only involves drawing straight lines.

DHMO

@MatsGranvik mathematics is not about numbers, nor is painting about ink, nor is music about notes.

18

skill patrol

good point^

Alessandro Codenotti

3:11 PM

@DHMO 0 is the minimum

DHMO

@AlessandroCodenotti sorry, I meant maximum

Alessandro Codenotti

that's right then

DHMO

so it's quite confusing

Alessandro Codenotti

all $\omega$ sequences in $\omega_1$ are bounded

DHMO

@AlessandroCodenotti why?

Alessandro Codenotti

3:13 PM

because $\text{cof}(\omega_1)>\omega$ ( that's not really an answer, I don't remember the standard proof, but you can get a contradiction by assuming that you have an unbounded one)

Leonhard Euler

Hello

DHMO

@AlessandroCodenotti I'm quite curious as to what $\text{cof}(\omega_1)$ would be

Alessandro Codenotti

$\omega_1$

DHMO

indeed

Alessandro Codenotti

an ordinal equal to its cofinality is called regular by the way

DHMO

3:16 PM

So the only regular ordinals are $\omega_a$ where $a$ is an ordinal?

Leonhard Euler

@BalarkaSen,Hello

Balarka Sen

h

Leonhard Euler

@BalarkaSen, how are you?

Balarka Sen

fine

Alessandro Codenotti

@DHMO not sure. There's also some choice involved in which ordinals are regular I believe, it's not a topic I know much about

DHMO

3:17 PM

@AlessandroCodenotti alright

I wonder how $\omega^\omega$ would look like

apart from, you know, a mess

Leonhard Euler

@BalarkaSen, could you please help me with the explanation of a geometry question?

Balarka Sen

no

maybe someone else can

Leonhard Euler

@BalarkaSen, why?

Balarka Sen

i don't want to

Alessandro Codenotti

3:36 PM

@BalarkaSen Ok I looked at some examples of reduced suspension to get an idea of how it is more well behaved than the usual one, I'm not sure why that solves the problem in this case though

Balarka Sen

@Alessandro Reduced cone, not suspension. The point is in a reduced cone there is no "vertex".

Or, rather, the vertex lies on the base itself.

Alessandro Codenotti

right, it looks like the usual cone with the vertex pushed to the base

So the reduced cone of $S^1\vee S^1$ looks like the wedge of $2$ half spheres rather than $2$ half spheres joined along a segment

Balarka Sen

Right. So the reduced cone on $H$ should be exactly a bunch of accumulating, inscribed hemispheres all touching at the bad point.

BAYMAX

there is a book of Abstract Algebra authour name starting from P , i don't remember the name ... any1 any idea , guess

Alessandro Codenotti

I'd say that's not simply connected though

Balarka Sen

3:46 PM

Paolo Aluffi, "Algebra: Chapter 0"?

BAYMAX

sorry no

I totally forgot his name

Balarka Sen

@AlessandroCodenotti Reduced cone of $H$? Sure it is! It's contractible, like the standard cone.

BAYMAX

ohh got got pinter

Alessandro Codenotti

Ah, wait, indeed it is

An hemisphere is a disk after all

Balarka Sen

mhm

Alessandro Codenotti

3:51 PM

@BalarkaSen I didn't know Aluffi's first name, is he Italian?

Balarka Sen

I don't know actually. He might be.

Alessandro Codenotti

He was born in Italy (graduated there then did a phd in the US) and has a dual Italian/American citizenship according to his website, interesting, I didn't know

Balarka Sen

Ahh