Lecture 2 (28.10.96)
Previous lecture:
Lecture 1 ,
Overview ,
Course home page ,
Representation of structures
We looked at different representations of strings and
graphs as relational structures.
-
A strings as a set of positions (natural numbers)
with linear order R_<, and unary predicates P_i for the
letters
(=standard representation of strings)
-
A string as a set of positions and letters, with unary predicates
for positions P_p, letters P_l, lienar order on positions R_,
and constants c_i for letters.
-
A graph with the vertices as universe and a binary relation R_E
for the edges.
(=standard representation of graphs)
-
A graph with set of vertices and edges as universe,
unary predicates P_v, P_e for vertices and edges,
and a ternary predicate for vertices beginning and ending an edge.
-
Exercise: find other representations for strings and graphs.
-
Using Second Order Logic to define strings
We gave examples on how to define
various regular languages, the languages a^nb^n and a^nb^nc^n
(not regular), hamiltonian graphs, 3-colorable graphs.
Exercise: Express connectivity, regularity, planarity
of graphs in both representations.
THEOREM
Regular languages are monadic second order definable
in the standard representation of strings.
Proof: Was given in detail.
The star-free regular languages are defined via regular
expressions.
Induction basis: The empty word, and each letter are starfree.
Induction closure: closed under and, or, negation and
concatenation.
THEOREM
Starfree regular languages are first order definable
in the standard representation of strings.
Proof: Was given in detail.
We want to prove the converse of these theorems.
For this we have to find criteria for definability.
Next lecture:
Lecture 3