What are appropriate isomorphisms between formal languages?

Question

A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are extensionally equal as subsets of $L\cup L'$. One can use languages in complexity theory to formalize the concept of a "problem." One could complain that "in general" extensional equality is undecidable, but I believe this would be misguided.

I'm pondering the following problem since some time: Two languages $L$ and $L'$ over alphabets $\Sigma=\{a,b\}$ and $\Sigma'=\{c,d\}$ (where $a$, $b$, $c$ and $d$ are distinct letters) can never be equal, even if they describe "exactly" the same "problem." But they should be isomorphic, if they really describe "exactly" the same "problem." What I would like to know are possible notions of isomorphism appropriate for complexity theory. I initially thought a computationally weak "translator" like a finite-state machine could be used to define the allowed isomorphisms, but this already seems to break down for trivial syntactic translations between equivalent logical formulas. (See for example this table with the syntactic definition of the dual $A^\bot$ in linear logic.)

Today I had the following idea: A definition of the language corresponding to a certain "decision problem" often has two parts: (1) An encoding of the allowed problem instances as finite strings of symbols, and (2) a definition of the "accepted" problem instances which belong to the language. If the checking whether a given finite string of symbols is an encoding of an allowed problem instance already requires a machine computationally stronger than a finite-state machine, then this stronger machine should also be used for the definition of the allowed isomorphisms.

Questions: Has this line of reasoning any chance of "resolving" my problem? Has my problem already been solved, so that I just need to read the right references? Does my problem itself makes any sense, or is this just as misguided as complaining about undecidability of extensional equality?

---

Edit (not an answer yet) I noticed that "(1) An encoding of the allowed problem instances as finite strings of symbols" already contains the (hidden) assumption of a normalized input. Without this assumption, two different finite strings might correspond to the same problem instance. Instead of checking whether a given finite string is valid, the checking might produce a normalized input (and map invalid strings to a special string).

This setting has the advantage that the machine doing the checking/normalization is already equipped with means to transform finite strings to other finite strings. The allowed machine (complexity class) for this task could be part of the problem definition, and the (iso)morphisms would use the same machine (complexity class). (The suggestion of "poly-time many-one reductions" from Raphael's comment would then indeed be one possibility for problems in $\mathsf{P}$.)

A drawback is that this way of specification might only be appropriate for deterministic machines. Non-deterministic machines might require more flexible ways to specify/decide whether two input strings correspond to the same problem instance.

Answer 1

Has my problem already been solved, so that I just need to read the right references?

The theory of abstract family of languages is relevant. For example, the morphisms defined by finite state transducers lead to the cone family. Eilenberg's short ICM talk from 1970 nicely explains this framework, see also chapter 11 "Closure properties of families of languages" from Introduction to Automata Theory, Languages, and Computation (1st ed.) by J. Hopcroft and J. Ullman from 1979. However, only nondeterministic languages fit into this framework¹. In the end, the book Theory of codes by J. Berstel and D. Perrin from 1985 helped me to come up with reasonable solutions for my problem. Codes and Automata by J. Berstel, D. Perrin and C. Reutenauer from 2009 is a major revision of this book with a much broader coverage.

Has this line of reasoning any chance of "resolving" my problem? Does my problem itself makes any sense, or is this just as misguided as ...?

The assumption that there is one correct category for modeling isomorphisms between languages to "formalize the concept of a problem" is misguided. There are many different categories which can be interesting in the context of formal languages.

Here are three interesting categories related to many-one reductions, which will be referred to as total, partial, and relational. The objects of the categories are pairs $(\Sigma, L)$ of a finite alphabet $\Sigma$ and a language $L\subset\Sigma^*$ of words over $\Sigma$. For total, the morphisms between the source object $(\Sigma, L)$ and the target object $(\Sigma', L')$ are total functions $f : \Sigma^* \to \Sigma'^*$ with $L=f^{-1}(L')$. For partial, the morphisms are partial functions $f : \Sigma^* \to \Sigma'^*$ with $L=f^{-1}(L')$, where two partial functions $f$, $g$ are considered equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$. For relational, the morphisms are relations $R\subset \Sigma^* \times \Sigma'^*$ with $L=R^{-1}(L')$, and any two morphisms between the same source and target are considered to be equal. The set of allowed functions or relations can be restricted to various simple "translators" to get categories with interesting isomorphisms.

• The monoid homomorphisms from $\Sigma^*$ to $\Sigma'^*$ give a very basic total category. The isomorphisms of this category are basically just the bijections between $\Sigma$ and $\Sigma'$. Any reasonable family of languages should better respect these isomorphisms, i.e. be closed under inverse homomorphisms.
• The partial functions defined by deterministic log-space Turing machine translators give a quite natural partial category. It is able to perform many trivial syntactic transformations (like applying De Morgan's laws to move negations to the atoms), includes the morphism defined by functional finite state transducers¹, and also can sort. Still it won't identify two completely unrelated languages as isomorphic, because equality of the composition of two morphisms to an identity morphism is a much stronger requirement than just existence of many-one reductions in both directions.
• The relations defined by nondeterministic log-space Turing machine translators give an interesting relational category. SAT is isomorphic to HORNSAT in this category, but it is an open question whether TAUTOLOGY or any other co-NP-complete problem is isomorphic to HORNSAT.

Two languages $L$ and $L'$ over alphabets $\Sigma=\{a,b\}$ and $\Sigma'=\{c,d\}$ (where $a$, $b$, $c$ and $d$ are distinct letters) can never be equal, even if they describe "exactly" the same "problem." But they should be isomorphic, if they really describe "exactly" the same "problem."

The very basic total category described above solves this problem.

The problem becomes more interesting if "exactly the same" is replaced by "nearly the same for most practical purposes": Let $L$ be a language over $\Sigma=\{U,C,A,G\}$ and let $L'$ be the language over $\Sigma'=\{0,1\}$ obtained from $L$ by the substitution $U \to 00$, $C \to 01$, $A \to 10$, and $G \to 11$. Note that in any total category, $L$ and $L'$ are not isomorphic for $L=\Sigma^*$. The same would be true for partial categories, if the part "where two partial functions $f$, $g$ are considered equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$" were omitted from the definition.

The quite natural partial category described above is sufficient for making $L$ and $L'$ isomorphic. It would be nice to have a more basic (i.e. more restrictive) category that makes them isomorphic. The following (successively more restrictive) categories look reasonable to me:

• The partial functions realized by unambiguous finite state transducers² where the only accepting state is the initial state. The isomorphisms of this partial category are (a subset of the) bijections between recognizable variable length codes.
• The partial functions realized by deterministic finite state transducers where the only accepting state is the initial state. The isomorphisms of this partial category are (a subset of the) bijections between prefix codes.
• The partial functions realized simultaneously by both a forward and a backward deterministic transducer where the only accepting state is the initial state. The isomorphisms of this partial category are (a subset of the) bijections between bifix codes.
• Further restriction of the partial functions such that the isomorphisms are (a subset of the) bijections between block codes could also make sense.

One can use languages in complexity theory to formalize the concept of a "problem."

Even before I learned about category theory, I have wondered about whether there are "more faithful" ways to formalize the concept of a "problem". After becoming familiar with category theory, I sometimes tried to come up with possible solutions, but always quickly gave up at the first stumbling block (because nobody cares anyway). I know that Yuri Gurevich has solved some related questions, but his solutions are practically applicable, whereas I was looking more for something nice and abstract, independent of practical applicability.

Most of my spare time for the last three weeks went into finally making some progress on this problem. Most often the time was spend finding annoying issues in the possible solutions I had in mind. The sense of making progress arose from reading (old) books and articles, and learning many basic concepts and facts about transducers and rational sets. Finally I learned the notions of a prefix code and a bifix code (formerly biprefix code in Berstel's book), which allowed me to come up with the reasonable³ categories described above.

It may be hard to appreciate those (code related) categories, without having seen some issues of the more obvious categories. A general issue is that closure under composition can make it hard to define a nicely restricted class of partial functions. Another issue is related to the fact that addition of one (or multiplication by a constant) is an "easy to compute function" if the digits of the number are given in low-endian order, but not if the digits are given in big-endian order.

---

1 _{A functional finite state transducer is a nondeterministic finite state transducer that realizes a partial function. These partial functions cannot be realized by deterministic finite state transducers. They can be realized by deterministic bimachines, but those may need $O(n)$ forward and backward scans over the input, if they want to operate in $O(1)$ space.}

2 _{An unambiguous finite state transducer is a nondeterministic finite state transducer with at most one accepting path for each input. It realizes a partial function, hence it is also a functional finite state transducer. It is decidable whether a given finite state transducer is unambiguous.}

3 _{I'm not sure how reasonable the total and the relational categories introduced above really are. I just wanted to show straightforward alternatives to the partial category. More alternatives are easy to come up with, for example co-relational, where the morphisms are relations $R\subset \Sigma^* \times \Sigma'^*$ with $L=R^{-1}(L')-R^{-1}(\Sigma'^*-L')$, and any two morphisms between the same source and target are considered to be equal.}