Koło Naukowe Matematyków U¦ PL SMS

IV SMS' Session
Automatas, grammars i formal languages.

Zarzecze, 12th - 15th November 1998

Session's Schedule

12 XI 98

14:55 Deaprture from Katowice. 
18:00 Arriving in Zarzecze. Accomodation. 
19:00 Opening of the Session - talk by dr Adam Kolanyu. 
20:00 Supper. 
20:30 Discussion: 
        Do people need help?
        Do we have truly poor people in Poland? Where truly means not by the conscious choice, but by neglect and lack of responsibility.
        Does being poor imply being worse? If not, why do we fight with poverty?

13 XI 98

9:00  Breakfast. 
10:00 Beginning of the morning talks session.
14:00 Diner.
16:00 Afternoon talk session.
20:00 Supper. 
20:30 Discussion 1: 
        Amnesty International - who gave them right to decide about human rights?
        Discussion 2:
        The reform of educational system by minister Mr Handke vs. changes that are really needed.
21:30 Games: checkers, chess etc.

14 XI 98

9:00  Breakfast. 
10:00 The beginning of the morning talk session. 
14:00 Dinner. 
16:00 Badminton and other sport games.
19:00 Discussion: 
The Act on student self-governments - the semantic and logic analysis.
20:30 Barbeque. 

15 XI 98

9:00  Breakfast. 
10:00 Visiting the neighbourhood.
12:00 Closing the Session - the talk by dr Marek Szyjewski
13:00 packing and cleaning. Dinner.
16:00 Departure to Katowice.

Łukasz Bujak
Radosław Czaja
Włodek Fechner
Agnieszka Furmankiewicz
Paweł Gładki
Renata Gołkowska
Adam Kolany
Michał Kolany
Mariusz Klęczar
Angelika Kurzyniec
Tatiana Korzeniowska
Izabela Papuga
Joanna Pawłowska
Bibianna Sonelska
Ola Stanek
Michał Trzęsiok
Żywilla Wcisło
Radosław Wieczorek
Marek Szyjewski

dr Adam KolanyCrinological study - accepterriers, computalsatians and turingweilers.
Żywilla WcisłoFinite State Automates, FSA. Examples: addition and multiplication tables; automata patching up equalities, inequalities etc.
Włodzimierz Fechner Deterministic and nondeterministic FSA. FSA with epsilon-movements. Bidirectional FSA. Equivalency of automata's classes.
Włodzimierz Fechner Moore's i Mealy's automates. Examples: converters between numeral bases etc.
Aleksandra Stanek Language accepted by FSA. Regular lanuages (RL). Equivalence of RL and languages FSA-acceptable. Examples of constructions.
Bibianna Sonelska Pumping lemma for regular languages. Examples of applications: unprogrammability os addres and multipliers.
Bibianna Sonelska Properties of RL. Closure properties. Decisional algorithms fo RL. Theorem on minimisation of FSA. (BS)
Łukasz BujakContext-free grammars (CFG). Examples. Alimination of epsilon-production, elimination of useless symbols.
Michał Trzęsiok Chomski and Greibach theorems about the normal form. Applications.
Tatiana KorzeniowskaPushdown automata (PDA). Deterministic pushdown atomata (DPDA). Acceptance: comparison between the empty stack and the finite state.
Tatiana KorzeniowskaEquivalence of NAZS and JBK. Examples of constructions.
Paweł GładkiThe pumping lemma for JBK and Ogden lemma. Applications. Properties of closures of JBK. Decision algorithms for JBK.
Radosław CzajaTuring's Machines (TM): (single-) double-sided unbounded; multi-paths; multi-belt; multi-imput; indeterministic. Equivalences of aforementioned.
Radosław CzajaCounting TMs.; Direct access machines, RAM; multi stage machines (MSM). Equivalence with the TM.
Joanna PawłowskaComputable functions and relations (CF na CR). Examples. Church proposition. Examples of uncomputable problems.
Joanna PawłowskaUniversal Touring Machine (UTM).
mgr Joanna Napiórkowska Rice theorem. Greibach theorem. Applications.
mgr Joanna Napiórkowska Oracle machines. Hierarchy of udecidable problems.
Renata GołkowskaChomski hierarchy. Chomski theorem on the hierarchy.
Joanna PawłowskaComputing complexity. PNP problem. NP-complete and NP-difiicultyof problems. Examples.

last update: 04.07.2012


Students' Mathematical Society of the University of Silesia
(Koło Naukowe Matematyków Uniwersytetu ¦l±skiego)
40-007 Katowice, ul. Bankowa 14 (room 524)
tel. (032) 359-20-96, email: knm@knm.katowice.pl