Project proposals for 236331
Previous update: April 29, 2001
Last update: April, 30, 2001
Back to Course homepage.
Below you find several project descriptions
suitable for the final project of
the course.
You should contact Julian Marino
in room 619 (TAUB, CS), Tel: 829 4873.
You can fix appointments by phone or e-mail
(julian@cs.technion.ac.il).
Projects need approval and several meetings with us are compulsory part
of projects
Definability/Complexity Catalogue
In these projects the task is to collect material
about one of the following problems,
and discuss its complexity and definability status.
- Reachability (in graphs).
Relevant literature:
-
Ajtai, Miklos; Fagin, Ronald;
Stockmeyer, Larry;
The closure of monadic NP. (English. English summary)
30th Annual ACM Symposium on Theory of Computing
(Dallas, TX, 1998).
J. Comput. System Sci. 60 (2000), no. 3, 660--716.
Journal.
-
Ajtai, Miklos; Fagin, Ronald; Reachability is
harder for directed than for
undirected finite graphs. J. Symbolic Logic 55
(1990), no. 1, 113--150.
Journal.
(Electronically available only via library of
Technion)
- Planarity of graphs.
Relevant literature
- Colorability of graphs
Relevant literature
- Hamiltonicity of graphs
Relevant literature
- Matchings
Relevant literature
- Eulerian circuits
Relevant literature
- Satsifiability of propositional logic
(coded as a graph)
Relevant literature
- The problem of your choice (after approval of
J. Marino or J. Makowsky)
In each of the following projects, the goal would be to
select material and prepare it for a 2-3 hour
presentation in the style of the course.
(Maximally material for 20 slides).
Picture languages
Picture languages are sets of rectangular coloured
(n x n) grids (like pixels on an (n x n)-screen).
There are several projects here:
- Find examples of picture languages which
are of particular interest.
Classify them by complexity (in P, NP, worse,
better),
by definability (in FOL, MSOL, ExistMSOL, SOL).
A specially amusing examples comes from the
MINESWEEPER game, and is NP-complete.
For futher reference you have to go to the new CS-LIBRARY.
Thanks to Yaron Welner for suggesting this project.
-
Richard Kaye, Minesweeper is NP-complete, The Mathematical
Intelligencer, volume 22.2 (2000), pp. 9-15.
-
D. Giammaresi, A. Restivo, W. Seibert and W. Thomas,
Monadic Second Order Logic over rectangular pictures
and recognizability by Tiling Systems,
Information and Computation, volume 125 (1996) pp. 32-45
Journal.
(Also electronically available via the library homepage)
- Characterize the ExistMSOL picture languages
via tiling systems.
Relevant paper are
-
W. Thomas, On Logics, Tilings and Automata,
ICALP 1991, LNCS volume 510 (1991) pp. 441-453.
(Not electronially available).
-
D. Giammaresi, A. Restivo, W. Seibert and W. Thomas,
Monadic Second Order Logic over rectangular pictures
and recognizability by Tiling Systems,
Information and Computation, volume 125 (1996) pp. 32-45
Journal.
(Also electronically available via the library homepage)
-
Discuss the quantifier hierarchy of MSOL for pictures.
Relevant papers are
definable picture languages.
-
O. Matz and W. Thomas, The Monadic Quantifier Alternation
Hierarchy over Graphs is Infinite, 12th LICS (1997), pp. 236-244.
ps-file.
-
N. Schweikhardt, The Monadic Quantifier Alternation Hierrachy
over Grids and Pictures, CSL 1996, LNC 1414 (1997), pp. 441-460.
ps-file.
-
O. Matz, N. Schweikhardt and W. Thomas, The Monadic Quantifier
Alternation Hierarchy over Grids and Graphs, to appear in
Information and Computation,
ps-file.
Quantifier prefixes of Second Order Horn formulas
In the course we showed that truth in structures
of existential second order Horn formulas can be done
in polynomial time. This is true for arbitrary
second order Horn formulas. In fact, every second
order Horn formula is equivalent to an existential
one. The proof of this is the content of this
project.
Relevant literature:
-
E. Graedel, Capturing Complexity Classes by Fragments
of Second Order Logic, Theoretical Computer Science,
volume 101 (1992) pp. 35-57.
P-reductions vs transducers in SOL Horn Logic.
See lecture from May 3, 2001
Project assignment
- Yaron Welner, Examples of Picture languages
including MINESWEEPER. Complexity and Definability of
each example.
final received: 18.11.01 grade 93
- Alexander Glikson Tree automata
and Monadic Second Order Logic
final received: 5.11.01 Grade 98
- Jonathan Ishai and Benjamin Sznajder
Quantifier prefixes of Second Order Horn formulas
final received: 04.12.01 Grade: Ishai 80, Sznajder 85
- Miriam Wallach SAT and its definability
and complexity
final received: 22.10.01 Grade 85
- Arieh Bibliowicz and Eitan Yoshuah
Datacompression and definability, after
Afrati, Leiss and de Rougemont
ps-file
final received: 04.12.01 Grade for both 90
- Yonit Magid Reachability in graphs
final received: 5.11.01 Grade 95
- Gilad Ben-Avi
Characterize the ExistMSOL picture
languages via tiling systems
final received: 14.12.01 Grade 90
- Ron Gross Connectivity and
Separability in graphs
final received: 10.10.01 Grade 90
- Ziv Nevo (No credit)
- Tamir Levy (dropped out)
- Valriya Bodnya ???
- Anna Kokoi ???
- Aharon Netz (dropped out)
- Dimitri Koyfman (dropped out)