Not signed in (Sign In)

Vanilla 1.1.9 is a product of Lussumo. More Information: Documentation, Community Support.


    While cleaning up tags, I noticed that we could make better use of some computer science arXiv categories to supplement the math arXiv tags that we already use.

    The most relevant categories appear to be the following:

    • cs.CC - Computational Complexity - Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
    • cs.CG - Computational Geometry - Roughly includes material in ACM Subject Classes I.3.5 and F.2.2.
    • cs.GT - Computer Science and Game Theory - Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
    • cs.CR - Cryptography and Security - Covers all areas of cryptography and security including authentication, public key cryptosytems, proof-carrying code, etc. Roughly includes material in ACM Subject Classes D.4.6 and E.3.
    • cs.DS - Data Structures and Algorithms - Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
    • cs.DM - Discrete Mathematics - Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
    • cs.FL - Formal Languages and Automata Theory - Covers automata theory, formal language theory, grammars, and combinatorics on words. This roughly corresponds to ACM Subject Classes F.1.1, and F.4.3. Papers dealing with computational complexity should go to cs.CC; papers dealing with logic should go to cs.LO.
    • cs.IT - Information Theory - Covers theoretical and experimental aspects of information theory and coding. Includes material in ACM Subject Class E.4 and intersects with H.1.1.
    • cs.LG - Learning - Covers machine learning and computational (PAC) learning. Roughly includes material in ACM Subject Class I.2.6.
    • cs.LO - Logic in Computer Science - Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
    • cs.MS - Mathematical Software - Roughly includes material in ACM Subject Class G.4.
    • cs.NA - Numerical Analysis - Roughly includes material in ACM Subject Class G.1.
    • cs.SC - Symbolic Computation - Roughly includes material in ACM Subject Class I.1.

    The categories cs.AI, cs.CL, cs.CE, cs.PL could be relevant to mathematics, but we don't seem to have a significant number of MO questions in these categories.




    Some of these cs categories are contained in existing math categories:

    Some already have cs tags:

    Finally, some existing tags match cs categories but aren't labeled as such:

    The tag [algorithms] partly matches cs.DS but also cs.CC and some other things. The tags [game-theory] or [combinatorial-game-theory] also partly match cs.GT but most game theory questions on MO are not directly related to CS per se.

    I think it would be a good idea to acknowledge the CS categories and create the four additional tags [], [cs.fl.languages-automata], [], [] (renaming the existing tags mentioned above). Some of these may be contentious, so please voice your concerns here or send an email to (The cs tag names are also debatable --- I did my best given the character limit imposed by the software.)


    The new tags [], [], [] have been created. We're waiting a bit for comments on cs.FL since merging two tags is irreversible.

    • CommentAuthorKaveh
    • CommentTimeJun 4th 2012

    Is it possible to drop the "cs." part from these tags? It would look nicer and more consistent with the other tags.


    We don't have [math.AT.algebraic-topology], for instance...


    The math tags are intended to match the arxiv category descriptions here (see the bottom of the ask page). The cs prefix is a hint to look at the arxiv category descriptions here instead.

    I think the cs prefixes are handy and would prefer they remain.
    • CommentAuthorJDH
    • CommentTimeJun 7th 2012
    François, could you clarify what the proposal is exactly? I am not clear on whether you are proposing merely to create additional tags with the cs prefix, which seems unobjectionable, or to completely abandon the tags such as "cryptography" and "formal-languages" in favor of those cs tags, which I would find objectionable.

    For many of the tags you mention, I don't view the cs angle on them as primary, and I would oppose the idea that the main tags would have a cs prefix. For example, I don't view formal-languages, automata or cryptography as owned more by cs than they are by mathematics. For example, it would absurd to allow cs.LO to be the main tag for logic here, and I view almost all the other tags in this same light. Even something like math-software is principally a math topic here as opposed to a cs topic, and the fact that the computer scientists are also interested in this topic doesn't mean that we must use their nomenclature.

    Dear Joel,

    The old tags [cryptography], [mathematical-software], [symbolic-computation] no longer exist, they have been renamed [], [], []. This is just a trial and this is completely reversible. (The [formal-languages] and [automata-theory] tags have not been touched since that would be irreversible.)

    The reasons you point out are exactly why I posted this. As I mentioned above, very few game theory questions have a cs angle, so it would be inappropriate to rename [game-theory] to []. A similar argument applies to logic, in fact the descriptions of math.LO and cs.LO are so different that it wouldn't be inappropriate at all for [lo.logic] and [cs.lo.logic] to coexist. For cryptography, mathematical software, symbolic computation, the descriptions of the cs categories seem to agree with how the community uses these tags. For formal languages and automata, the main issue is that these are conceptually very different though one hardly ever goes without the other.

    I find your objection to the cs prefix interesting. I'm glad you mentioned it. In my mind, all MO tags have an implicit math prefix because all MO questions are primarily about mathematics. (Questions that are primarily about cs should be redirected to or To me, the cs prefix only indicates that the cs angle is relevant. If most users think that the cs prefix indicates that the topic is primarily cs, then I see that as a good reason to eliminate all cs prefixes!

    • CommentAuthorJDH
    • CommentTimeJun 7th 2012 edited
    I think we've made a mistake in replacing the cryptography tag with and similarly with the other cs prefix tags. Since mathoverflow is a mathematics site, the existence of a cs prefix tag here seems suitable only for those topics where the cs angle is dominant over the mathematics angle. But this is not the case for most of the tags mentioned here. For example, I would prefer complexity-theory to, unless one was interested explicitly in a computer science as opposed to mathematics angle on complexity theory.

    I guess my view can be summarized as: the fact that the cs arxiv has a system of tags is not so relevant for our tag usage here on MO, even though many of us are interested in topics connected with computer science. The cs tags should be used only for topics that are not covered well by explicitly mathematical tags. And I would perhaps recommend changing some of the recent changes back.

    That's a good point, Joel. We'll wait a few days for people to voice their opinions...

    If we decide to eliminate cs arxiv prefixes, then we will go forward with the following tag renamings:

    • [] -> [computational-complexity]
    • [] -> [computational-geometry]
    • [cs.lg.learning] -> [learning-theory]
    • [] -> [cryptography]
    • [] -> [mathematical-software]
    • [] -> [symbolic-computation]
    • CommentAuthorKaveh
    • CommentTimeJun 7th 2012 edited

    I agree with what JDH wrote. For me the "cs." prefix creates the feeling that these topics are kind of different from the rest of the topics, that they are inferior or not suitable for MO.

    I also personally prefer if the mid-fixes are included in the tags, e.g. "cc.complexity-theory" in place of "complexity-theory" to keep their distinction from other tags. These are areas like other areas in mathematics, I don't see a reason to differentiate between these and other area tags, they should be treated the same way other area tags are treated IMHO.


    I second what Kaveh says in the second paragraph.


    That seems problematic since math.CC is not an arXiv category. Maybe (as the cs prefix did for Joel) the two-letter prefixes mean something different to you than they do to me?


    I don't understand what role the two-letter prefixes play in any of the tags. For example, why not change "nt.number-theory" to "number-theory"? The "NT" in the arXiv is just a space-saving abbreviation for "number theory" anyway, and it seems silly to use the abbreviation at all if you're always going to append the full name. Right now, the only role the prefixes seem to play is as a mildly obscure way of emphasizing that these are the same categories as on the arXiv. However, with the exception of ho.history-overview (where the usage of the category on the arXiv is broader than one might expect from the name), I don't think see any real content here. It's not like someone's going to say "Oh, I get it, you mean number theory as in the arXiv!"


    Good point, Henry. Is it the case that arxiv tags have served their purpose and are no longer needed on MO?

    For the curious, the historical origin of arxiv tags is documented in this thread from 2009:


    Rereading the 2009 thread linked above, the basic idea was to have some reference list of "major tags" for classification purposes. (The term "major" here is used in opposition to "specialized" but not as broad as [analysis], [algebra], [geometry], or even [math] which do very little for classification purposes.) An ideal classification system would be such that every MO question would fit into one or more of these major categories, excluding off-topic questions. The consensus was that the math arxiv tags would serve that purpose well and they did for quite some time. It does appear that MO has outgrown this classification system.

    This brings us to some basic questions:

    1. Does MO still need major categories?
    2. If so, what would be the list of major tags and how would it be maintained?
    3. And how would one distinguish major tags from more specialized tags?

    Note that, as a result of the 2009 discussion, a list of arXiv tags was added at the end of the ask form, and the front page has this notice: "Want to help? Consider retagging questions with no arXiv tag."

    (I edited the title since this the topic is shifting to arXiv tags in general.)

    • CommentAuthorKaveh
    • CommentTimeJun 8th 2012


    Regarding 1, I think there is a need to have a small number of major tags. The number of questions posted on MO has become so huge that these subject classification tags seem essential to have a simple and easy way of following questions in topics we are interested in.

    Regarding 3, an easy way could have been using a "." and dropping the the preceding two letters, but unfortunately the software doesn't allow tags starting with it AFAIR. Btw, you might be interested in the following simple user-script I wrote sometime ago for making these tags more distinguishable from the rest: Bold and colorful area tags

    • CommentAuthorWillieWong
    • CommentTimeJun 11th 2012

    One of the problem that is nicely addressed with the arXiv tags is that it solves the problem of the tags being not otherwise defined (which can be problematic coupled with the character-number limit in the tag names; compare [ca.analysis-odes] to [pseudodifferential-oper]--incidentally this also gives a partial counterexample to Henry Cohn's assertion that we almost append the full name).

    Another particular strength of the arXiv tags is that the list is remarkably short. Imagine requiring using something like the MSC2010 for the tags! So for question 1, I agree with Kaveh that there needs to be a small number of major tags.

    • CommentAuthorGjergji
    • CommentTimeJun 11th 2012
    I also support the idea of two types of tags, the math arxiv ones and the more specific tags. They play very different roles so I think it's good that the arxiv tags are kept as XY.x-y to distinguish them from the rest.

    Some of us are used to browsing subjects by arxiv categories not only on arxiv itself but also on several blogs (and of course MO). The more specific tags are useful when restricting to very specific topics.

    One reason why I want all questions to be tagged with at least one arxiv tag is that when specifying interest tags, I am more likely to pick a broad subject, such as "combinatorics" or "probability", and I don't want to have to update my list every time a new tag is created that would fit in these categories. I think arxiv tags are very easy to use in this context because people are already very familiar with this categorization.

    Specific tags, on the other hand, are useful for search purposes. For instance, if I want to gather a quick collection of combinatorial identities, say, than I can look through the questions tagged accordingly.
    • CommentAuthorHJRW
    • CommentTimeJun 14th 2012

    +1 Gjergji.


    Tomorrow I will rename the last two CS tags:

    • [] -> [computational-complexity]
    • [] -> [computational-geometry]

    Regarding arxiv tags in general, there are varying opinions. I think there are some important issues with arxiv tags but it might be better to keep the status quo until we migrate to SE 2.0.


    Francois, I should say that tag renaming and deletion abilities are considerably reduced in SE 2.0, at least for "local" moderators. If there is going to be a migration at some point, I suppose tag cleanup should be done before that.


    Asaf, how are they limited?


    The first thing I know is that it is not longer possible to delete tags (without retagging).

    I also believe that renaming also suffers from this issue (we had a recent decision to change [filter] to [filters] and we had to do it manually, despite moderators being involved, it ).

    I'm sure that one of the MSE moderators that writes here could be more helpful, but I do recall that some privileges were taken away.

    • CommentAuthorWillieWong
    • CommentTimeJul 27th 2012

    Asaf receives a score of 1 right and 1 wrong.

    It is no longer possible to Nuke tags in SE2 without intervention by an employee. That is, Community Mods cannot nuke tags.

    Renaming can be done using the merge tool. Earlier last calendar year I pluralised quite a few tags at the request of Theo Buehler, so that is definitely possible.

    • CommentAuthorKaveh
    • CommentTimeJul 30th 2012 edited

    @François, Can you make [cc.complexity-theory] a synonym for [computational-complexity]? Similarly [cg.comp-geometry] -> [computational-geometry] and [cr.crypto] -> [cryptography].


    Kaveh, I would love to but synonyms are a SE2 feature.