4
$\begingroup$

I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this?

I wrote "double language" first (but that doesn't sound right to me), then "square language" (but languages can be squared in various ways), then "pair language" (maybe ok?), or just "language". The issue with just "language" is that it doesn't convey that there's a sort of "type hierarchy" of languages, which would be useful for me (just informally that is, don't read too much into the word "type", I barely know what it means). Eventually I figured maybe someone has already called this something and I should use the same.

My paper is in symbolic dynamics (or something like that), where I think no term is fixed for this. I am sure I have seen such "languages" in the theory of formal languages, in automata theory, and in combinatorics on words, but I can't really put my finger on any specific reference where they play a prominent role.

You can also just give your expert (or other) suggestion.

Improve this question
$\endgroup$
3
  • $\begingroup$ If I understand your question properly, the word you are looking for is "transducer". See here:en.wikipedia.org/wiki/Finite-state_transducer $\endgroup$
    – Faustus
    Mar 29, 2021 at 9:28
  • 1
    $\begingroup$ That's an interesting point, indeed a transducer gives rise to such an object. However, it does not seem correct in my situation, $(u,v) \in L$ does not mean that $v$ is produced in any way from $u$, even intuitively (actually these words end up representing coordinates in a Cantor set). But your point suggests that something like "relation language" would be yet another possibility. $\endgroup$
    – Ville Salo
    Mar 29, 2021 at 9:33
  • $\begingroup$ I was gonna suggest relation or relation language, but you already got there, so I'm just recording this here as a vote for that terminology. $\endgroup$
    – Joshua Grochow
    Mar 29, 2021 at 18:19

0

Reset to default

Your Answer

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