Can formal language theory be correctly characterized as a branch of discrete mathematics?

91 Views Asked by At

Can formal language theory be correctly characterized as a branch of discrete mathematics?

If so, what is the correct antonym for "discrete" here?

Reason I'm asking is that for rhetorical purposes in a draft paper, I need to contrast language-theoretic objects with objects such as quadrics and manifolds arising in "non-discrete" mathematics.

In this regard, see these questions:

Suppose it can be shown that any right(left)-regular finite-state grammar implicitly generates a "hypar"" surface

Is there any surface approximation algorithm which uses "hypar" patches only?

Hyperboloids of one sheet, hyperbolic paraboloids, and Hilbert's famous "three skew lines"

2

There are 2 best solutions below

1
On BEST ANSWER

To answer your question, let me quote a part of Wikipedia entry for Discrete Mathematics concerning number theory.

Number theory is concerned with the properties of numbers in general, particularly integers. (...) Other discrete aspects of number theory include geometry of numbers. In analytic number theory, techniques from continuous mathematics are also used. Topics that go beyond discrete objects include transcendental numbers, diophantine approximation, p-adic analysis and function fields.

I would say that the situation is similar for formal languages. Formal languages do belong to Discrete Mathematics, but some tools go beyond discrete objects.

Indeed, formal language theory makes use of topology, especially profinite topologies. See for instance the papers Duality and equational theory of regular languages and A Topological Approach to Recognition. By the way, this approach shares some analogy with the $p$-adic metric on the integers. For instance, the $p$-adic metric can be extended to words: see the paper (in French) Topologie $p$-adique sur les mots or Thue sequence and p-adic topology of the free monoid.

1
On

While I agree that one could not use the adjective continuous as an antonym of the adjective discrete in this context (although the two terms are at least roughly antonymic in other contexts, even within mathematics), I think one could nevertheless use the noun phrase mathematical analysis (although this would admittedly be in an uncomfortably extended sense) as an approximate antonym of the noun phrase discrete mathematics. (But whether a phrase can legitimately be called an 'antonym' of another phrase is another question!) I also agree that formal language theory belongs to the latter.