3
$\begingroup$

Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$.

I am wondering if there is some good terminology for

$L\cap\Sigma^n$.

Of course I could say "the set of words in $L$ of length $n$" but maybe there is some special terminology like "level set of length", "grade", "homogeneous section" or I don't know what.... ?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Nope. No special terminology (to my knowledge) apart from "the set of words from $L$ with length $n$" $\endgroup$ – nir shahar Feb 25 at 23:53
  • 3
    $\begingroup$ The closest thing I know is the concept of a slice in parameterized complexity, which is explained e.g. here. One could argue that using the normal coding length as a parameter the set $L \cap \Sigma^n$ is the $n$th slice of $L$. $\endgroup$ – Watercrystal Feb 26 at 9:55
  • 1
    $\begingroup$ Yes, some of the names that you mention are used. $\Sigma^*$ is the free monoid over the $\Sigma$. A free monoid is a graded monoid by the monoid homomorphism $d:\Sigma\to\mathbb{N}$, defined as $d(\Sigma^n)=\{n\}$. The elements of $\Sigma^n$ are called the degree $n$ elements. $\endgroup$ – plop Feb 26 at 15:43
  • $\begingroup$ @Watercrystal "slices" sounds good, if it's not used a lot maybe it should be used more. I'll accept it as an answer. $\endgroup$ – Bjørn Kjos-Hanssen Feb 26 at 19:59
  • 1
    $\begingroup$ That's a name that people use, yes. It would always need to be defined before using, but well. $\endgroup$ – plop Feb 26 at 20:26

Your Answer

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

Browse other questions tagged or ask your own question.