Substitution of expressions in a symbolic expression

I define tables of symbolic variables in the following form (for convenience)

X = Table[Symbol["x" <> ToString[i]], {i, 1, num}]; Y = Table[Symbol["y" <> ToString[j]], {j, 1, num}];  

And after that, in cycles, I create some expressions. For example, here is one of them

Expon := Exp[ - ((X[[1]] * Y[[1]]) / 4) ];  For[i = 2, i <= num, i++,  Expon = Expon * Exp[ - ((X[[i]] * Y[[i]]) / 4)] ]  

After that, I want to act by some differential operator on my symbolic expression (let’s call it $ \Psi$ ) and substitute in the final expression some tables of numbers X1 and Y1 (here they are not symbolic, but filled by real numbers). I tried to use ReplaceAll ./ command, but it didn’t work. Could you tell me please, how can I substitute two or more tables of real numbers in symbolic expression? Long story short, how to calculate something like $ \Psi(X1, Y1)$ ?

What is the difference between available expressions analysis and very busy expressions analysis?

I am having trouble understanding the conceptual meaning of the two kinds of analysis. I know the equations and how to solve the problems and I know how one is a forward data-flow analysis while the other is a backwards data-flow analysis, but there is still something missing in the explanations I have seen so far, in a higher level.

What is the computational complexity of “real-life” regular expressions?

Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), and the Kleenee star x*.

"Real-life" regular expressions as used in programming usually have a lot more operations available; amongst others, quantification x{n}, negation [^x], positive and negative lookahead x(?=y), or back-reference \n.

There is a famous post on SO stating that regular expressions can not be used to parse HTML for the reason that HTML is not a regular language.

My question is: Is this accurate? Do "real-life" regular expressions, say the selection defined in the Java docs, really have the same expressive power as regular expressions as understood in formal language theory; or do the additional constructs, although possibly not strong enough to capture HTML and the like, put common regular expressions further up on the Chomsky scale than just Type 3 languages?

I would imagine the proof of the computational equality of the two would amount to showing that each operation available for the common regexp is just syntactic sugar and can be expressed by means of the 3 basic operations (concatenation, alternation, Kleene start) alone; but I am finding it hard to see how one would e.g. simulate back-reference with classic regexes alone.

Symplifying expressions with exponentials inside square root

I have an expression $ $ \exp (i k x) \sqrt{y^2 \exp (-2 i k x)} $ $ When I put this in Mathematica and do FullSimplift, it gives

FullSimplify[Exp[I k x] Sqrt[Exp[-2 I k x] y^2]] 

The output is $ $ e^{i k x} \sqrt{y^2 e^{-2 i k x}} $ $ Even if I give all proper assumptions $ \{x,y, k\} \in \mathbb R$ and $ -\pi < k \leq \pi$ like this

FullSimplify[Exp[I k x] Sqrt[Exp[-2 I k x] y^2], {x, y, k} \[Element] Reals && -\[Pi] < k <= \[Pi]] 

The output comes as $ $ \left| y\right| e^{i k x} \sqrt{e^{-2 i k x}} $ $ But the exponentials should not be there anymore, the result should be only $ \left| y\right|$ .

What simplification or assumptions to make, to get the desired result?

Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials

Let’s have expressions that are composed of elements of $ \mathbb N$ and a limited set of binary operations {$ +,\times,-,/$ } and functions {$ \exp, \ln$ }. The expressions are always well-formed and form finite trees, with numbers as leaf nodes and operators as internal nodes, binary operations having two child sub-expressions and the functions one. A value of such an expression is interpreted to mean some number in $ \mathbb R$ .

There are two limitations on the structure of the expressions: the divisor (the right-hand sub-expression) of $ /$ can’t be 0 and the argument of $ \ln$ must be positive.

I have two questions about these kind of expressions:

  • Is it possible to ensure “soundness” of such an expression, in the sense that the two limitations can be checked in limited time?

  • is an equality check between two such expressions decidable?

These questions seem to be connected in the sense that if you’re able to check equality of the relevant sub-expression to zero, you can decide whether a division parent expression is sound, and it doesn’t seem hard to check whether a sub-expression of $ \ln$ is positive or negative if it’s known not to be zero.

I know that equality in $ \mathbb R$ is generally not decidable, whereas equality in algebraic numbers is. However, I wonder how inclusion of {$ \exp, \ln$ } changes the result.

(A side note: I posted an earlier version of a question with similar intent here, but it turned out to have too little thought behind it, and had unnecessary (= not related to the meat of the question) complications with negative logarithms.)

Decidability of equality of expressions involving exponentiation

Let’s have expressions that are finite-sized trees, with elements of $ \mathbb N$ as leaf nodes and operators and the operations {$ +,\times,-,/$ , ^} with their usual semantics as the internal nodes, with the special note that we allow arbitrary expressions as the right-hand side of the exponentiation operation. Are the equality between such nodes (or, equivalently, comparison to zero) decidable? Is the closure under these operations a subset of algebraic numbers or not?

This question is similar to this: Decidability of Equality of Radical Expressions but with the difference that here the exponentiation operator is symmetric in the type of the base and the exponent. That means that we could have exponents such as $ 3^\sqrt 2$ . It isn’t clear to me, whether allowing exponentiation with irrationals retains the algebraic closure.

This question is also similar to Computability of equality to zero for a simple language but the answers to that question focused on the transcendental properties of combinations of $ \pi$ and $ e$ , which I consider out of scope here.

Factoring long trigonometric expressions separating specific variables

I have a very long expression with trigonometric functions:

n (2 a - h - 2 z) (-Sin[p (β - δ + t ω)] + Sin[p (β + δ + t ω)]) 

I would like to simplify the term (-Sin[p (β - δ + t ω)] + Sin[p (β + δ + t ω) to 2 Sinδ Cos (ωt + β).

Any suggestions? Just using Simplify does not work on this case. Thank you for your help.

Is there an abstract architecture equivalent to Von Neumann’s for Lambda expressions?

In other words, was a physical implementation modelling lambda calculus (so not built on top of a Von Neumann machine) ever devised? Even if just on paper?
If there was, what was it? Did we make use of its concepts somewhere practical (where it can be looked into and studied further)?

— I’m aware of specialised LISP machines. They were equipped with certain hardware components that made them better but eventually they were still the same at their core.

If there isn’t such thing, what stops it from being relevant or worth the effort? Is it just a silly thought to diverge so greatly from the current hardware and still manage to create a general-purpose computer?

Arden’s Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden’s Rule and the equational method to transform DFA’s & NFA’s to RE. I know what the rule state:

if x = s + xr
then x = sr*, with $ s,r\in$ Regular Expressions

With that said, when I’m trying to transform one DFA in a RE this questions pop:

For example regarding this DFA

  1. The $ \epsilon$ is added in the entry stage A or in the final stage D and A ?

  2. The equations should be written regarding the transitions in or out of a given state

    2.1 For example A = $ \epsilon$ + 0B + 1C or A = $ \epsilon$ + 0C

  3. Can the equational method and Arden’s Rule be applied to a NFA with multiple initial states ?

Final thoughts, I have been trying out and it seems that when we count the transitions out of a state the $ \epsilon$ should be added to the final state. When we count the transitions into a state the $ \epsilon$ should be added to the initial state.

Keep in mind that I SERIOUSLY doubt my conclusions and I really need some help.