I have a function that takes a set as a parameter. The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" of $x$. $R$ one-to-one represents grammars generating a single string $s \in \Sigma^*$.

$$ \phi(x, A) = \begin{cases} 0, \text{ if } x \in A \\ |x_t^*| + n(x) - \sum\limits_{i=1}^{n(x)} \phi(x_i, A), \text{ if } x \notin A, \text{ and, } \\ \text{ also ensure, } A := A \cup x \end{cases} $$

So as you can see the value of successive calls to $\phi$ depend on the contents of the set $A$. $A$ is passed-by-reference (not by value copy).

Was wondering if math has a formalism for dealing with such functions that depend on a persistent set parameter.

It's true that if we let $|0^*| = |\epsilon| = 0$ that the size of a grammar $x + y$, for $xy = 0$ (empty intersection), is $$\psi(x + y) = |s| - \phi(x + y, \{\}) = \\ (\text{init } A:=\{\})\\ |s| - (\phi(x, A) + \phi(y, A))$$.

So that $\phi(z, A)$ acts a like a measure for disjoint elements $xy = 0$ of $R$. But as you know, measure functions don't usually take a lookup set as a parameter. So was wondering about the best formalization.


Your $\phi$ is stateful; the value of $\phi(x,A)$ depends on what parameters you have previously evaluated it with. As such, it is not a mathematical function. Mathematical functions are stateless.

Formalization serves a purpose: to describe clearly and precisely. It's not to blindly follow rules, but to serve as an aid to communication. As long as you have described what you want clearly and precisely, in a way that a reader is likely to understand, you are good. So, don't call $\phi$ a function, as that will confuse readers; but you can describe the intended semantics of what you want the procedure $\phi$ to return, in terms of its parameters and its state.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.