## Unit Overview – Language Complexity

David A. Tanzer, January 2021, in unit Language Complexity

How complex is the English language? That’s a tough nut to crack. Here we’ll reframe the question in a more formal setting which is shared by computer science and linguistics: the theory of formal languages and their complexity. By the end, we’ll reach a technical understanding of what is meant by the famous conjecture P != NP.

## Language Complexity, Part 1

David A. Tanzer, January 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

A simple view of languages

How complex is the English language? The question has many dimensions and nuances. What does complexity mean, and how could it be measured? This a tough nut to crack, so in this post we’ll make a retrenchment and reconsider the question in a more formal setting — computer science.… Read more

## Language Complexity, Part 2

David A. Tanzer, January 30, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Decision problems, decision procedures and complexity

In Part 1, we introduced the formal idea of a language, as being just a set of sentences. Now let’s approach the topic of language complexity.

For any given language, there is an associated decision problem:   given a candidate string of characters, determine whether or … Read more

## Language Complexity, Part 3

David A. Tanzer, February 7, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

A detailed measure of computational complexity

In Part 2, we identified language complexity by how “difficult” it is for a program to decide if some given text is a sentence of the language — in other words, by the complexity of the decision problem for the language.

Note there may be many … Read more

## Language Complexity, Part 4

David A. Tanzer, February 8, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Summarizing computational complexity

In Part 3 we defined, for each program P, a detailed function P'(n) that gives the worst case number of steps that P must perform when given some input of size n. Now we want to summarize P into general classes, such as linear, quadratic, etc.

## Language Complexity, Part 5

David A. Tanzer, February 9, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Big O analysis

Recall our function $f(n)$ from Part 4, which gives the values 2, 13, 14, 25, 26, 37, …

Using ‘big O’ notation, we write $f(n) = O(n)$ to say that $f$ is linearly bounded.

This means that $f(n)$ will eventually become less than some linear function.

As we said, … Read more

## Language Complexity, Part 6

David A. Tanzer, February 10, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

In Part 5 we introduced big O notation for describing linear complexity. Now let’s look at a function with greater than linear complexity.

def square_length(text):
# compute the square of the length of text
# FIXME: not the most elegant or efficient approach
n = length(text)
counter = 0
for i 

## Language Complexity, Part 7

David A. Tanzer, February 11, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Higher complexity classes

In Part 6, we saw a program with quadratic complexity. The collection of all languages that can be decided in $O(n^k)$ time for some $k$ is called P, for polynomial time complexity.

Now let’s consider languages that appear to require time that is exponential in the size of the input, … Read more

## Unit Overview – Epidemic Models 2

David A. Tanzer, August 2020, in unit Epidemic Models 2.

In Epidemic Models 1, we introduced compartmental models, leading to the SEIR model, which is used for epidemics like Covid. The discussion there, however, was structural and qualitative. In this unit, we take the next step with these models, which is to analyze their dynamics – this will account for the rates at which the epidemic “moves” individuals … Read more

## Epidemic Models 2, Part 1

David A. Tanzer, August 17, 2020, in unit Epidemic Models 2.

# The rates matter

In the last series, we introduced the idea of a reaction network, which is a collection of processes that are moving individuals between the compartments. What was missing there, though, was any kind of description of how fast the reactions run. This has a significant impact on the overall behavior of the network.