This is an old revision of the document!

Playground

Problem 1: Linear Extension

Let $r\subseteq A\times A$ be an arbitrary relation and $\leq$ a partial order on $A$ .

a) Assume $a,b\in A$ to be incomparable: $a\not\leq b$ and $b\not\leq a$ . Show that the transitive closure of the relation $r_{\text{ex}}$ is a partial order on $A$ .

$r_{\text{ex}} = \{(x,y) | x\leq y\}\cup\{(a,b)\}$

b) Use (a) to show if $A$ is finite then every order $\leq$ on $A$ has a linear extension. A total order $\leq_{1}$ is a linear extension of a partial order $\leq$ if, whenever $x\leq y$ implies that $x\leq_{1} y$ .

c) Use (a) to show there is a finite number of total orders $(A,\leq_1),\cdots,(A,\leq_n)$ such that for all $a,b\in A$ we have

$a\leq b \Leftrightarrow (a\leq_1b \wedge\cdots\wedge a\leq_n b)$

d) Show that $\leq_1$ is a linear extension of $\leq$ if and only if $(A,\leq_1)$ is a total order and the identity function is a monotone function from $(A,\leq)$ to $(A,\leq_1)$ .

Perl

Write a regular expression that matches a pair of <d> and </d> XML tags and the text between them. The text between the tags can include any other tags.

The lexical analyzer typically finds the longest matches. Some languages such as Perl have introduced laziness in matching. By adding a question mark to the end of an operator its lazy version is obtained. For example, given an input 'aaaaa', the expression $a*$ will match the entire input. But the lazy version $a*?$ matches the minimum number of possible characters, which is the empty string. Using lazy repetition find a compact representation for the first part.