2
$\begingroup$

I've worked with this theory for a while, but I've never been quite sure what to call it:

$$(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$$

Where

  • $\Sigma^*$ is the set of finite words on finite alphabet $\Sigma$
  • $x =_{el} y$ if $x$ and $y$ are equal length
  • $x \preceq y$ if $x$ is a prefix of $y$
  • $S_a(x)$ is $x$ concatenated with the letter $a$, for $a \in \Sigma$

"Decision Problems for Multiple Successor Arithmetics" (J.W. Thatcher) gives it the very generic name $N_k(r, \preceq, L)$.

"Relations Over Words and Logic: A Chronology" (C. Choffrut) attributes this logic to Eilenberg, Elgot and Shepherdson, and points out a paper where it's called $\mathbf{S}_\text{len}$, but this also seems to be a generic name.

For comparison, the equivalent weak monadic second order logic of one successor has a fairly standard name and abbreviation (WS1S), making it easy to search.

Does anyone who works with these sorts of logics have a preference for what to call this structure?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ As everybody working with combinatorics on words, I work with this logic. I do not have any preference for the name, as far as I am concerned, you are free to call it anything you want. $\endgroup$
    – markvs
    Commented Jul 29, 2021 at 3:45
  • $\begingroup$ You might ask at the appropriate conputer science question site. Most people I know who do logic on words are computer scientists $\endgroup$
    – Benjamin Steinberg
    Commented Jul 29, 2021 at 15:00
  • $\begingroup$ Just two remarks. As you are free to adopt any name and notation you want (providing you define them for the poor reader :), I would suggest to use $\equiv_{el}$ rather than $=_{el}$, because this is not an equality (for alphabets with more than two letters) and precise where the $a$ is concatenated (left of right ?). I have a preference for the left for your $S_a$ because of the latin "sinistra". $\endgroup$
    – Duchamp Gérard H. E.
    Commented Apr 12, 2022 at 2:25

0

Reset to default

You must log in to answer this question.