I'm reading this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi= or http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf

On page 1101 are introduced 2 functions without a precise definition. It is said that they are functions of the type $\textrm{f}:\mathbb{A} \rightarrow \mathbb{N}$ where $\mathbb{A}$ is a set. For example $\mathbb{A}$ can be a concept or an instance. For regular languages an instance can be a string on the alphabet and the concept a specific DFA (between all DFA on that alphabet) (alternately the concept can be defined as a subset of the set of sets made of all subsets on all the possible instances (namely a subset of $2^X$ where $X$ is the instance space namely all the possible instances). The instances on the subset are the $accepted$ instances, the others are $rejected$ ).

(http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1655&context=cse_research for precise definitions of instance and concept, look at definitions)

The 2 functions are : $\vert \bullet \vert$ that works on a instance (for example a string). Does mean this function? Can be the length of that instance?

The other function is : $\lVert \bullet \rVert$ and works on a concept (namely yours input is a concept). But I'm not able to imagine what this function means in this context and in the paper isn't explicated.

  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$
    – D.W.
    Jul 5, 2017 at 18:37

1 Answer 1


The only property that the functions $|\cdot|$ and $\|\cdot\|$ need to satisfy is that for every $n$ there is a finite number of $x$'s in the domain such that $|x|=n$ or $\|x\|=n$. The difference between the two is the domain: $|\cdot|$ is defined on $\mathcal{X}$ while $\|\cdot\|$ is defined on $\mathcal{C}$.

These functions are instantiated on page 1115: for $\mathcal{X} = \Sigma^*$, $|\cdot|$ is the length of the word; and for $\mathcal{C}$ being the set of all DFAs on $\Sigma$, $\|\cdot\|$ is the number of states.

  • $\begingroup$ Thank you very much! Maybe the authors could think of putting these two functions into definitions before introducing them! $\endgroup$
    – Nick
    Jul 5, 2017 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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