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.... ?

$\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, 2021 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$ Feb 26, 2021 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, 2021 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$ Feb 26, 2021 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, 2021 at 20:26

0

Your Answer

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

Browse other questions tagged or ask your own question.