(directed by D. Poulakis and G. Rahonis)
April 24, 12:30, Computers' Lab
Prof. Jelena Ignjatović,
Department of Mathematics and Computer Science
University of Niš, Serbia
Fundamental Problems of Fuzzy Automata Theory (lecture) 

Over the decades, fuzzy relations have gained a wide range of applications and here we will consider their application in the theory of fuzzy automata. The key point is that a fuzzy automaton can be regarded as a fuzzy relational system. This way of viewing, enables to study fuzzy automata using fuzzy relational calculus and to express many problems through fuzzy relation equations and inequalities. I will present several fundamental problems of the fuzzy automata theory. The first fundamental problem is determinization of fuzzy automata. The second one is state reduction problem which can be reduced to the problem of solving some specific systems of fuzzy relation equations and inequalities and the third problem is whether two automata simulate each other and it is closely related to the problem of equivalence of the two given automata. 
April 23, 17:10, Room H6 Department of Computer Science
Prof. Makoto Tatsuta, National Institute of Informatics, Japan
Brotherston's Conjecture: Equivalence of Inductive Definitions and Cyclic Proofs 

An inductive definition is a way to define a predicate by an
expression which may ontain the predicate itself. The predicate is
interpreted by the least fixed point of the defining equation.
Inductive definitions are important in computer science, since they
can define useful recursive data structures such as lists and trees.
Inductive definitions are important also in mathematical logic, since
they increase the proof theoretic strength. MartinLof's system of
inductive definitions given in 1971 is one of the most popular system
of inductive definitions. In 2006 Brotherston proposed an alternative formalization of inductive definitions, called a cyclic proof system. In general, for proof search, a cyclic proof system can find an induction formula in a more efficient way than MartinLof's system, since a cyclic proof system does not have to choose fixed induction formulas in advance. The equivalence of the provability of MartinLof's system for inductive definitions and that of the cyclic proof system was conjectured in 2006. The speaker and Berardi solved it last year. This talk will explain this problem from basic background knowledge to the latest results. 
March 13, 09:15, Computers' Lab
A computational
model for the contribution of zonulin to the development of cancer and
autoimmune diseasesng regular languages using queries 

Master Thesis presentation. 
February 22, 11:00, Computers' Lab
Lerning regular languages using queries (lecture) 

Language identification is a branch of machine learning where the target function represents a regular language. More precisely, we present the model of online learning using queries and focus on the learning procedure that is used in the L* algorithm, introduced by Dana Angluin, as well as some variations of it. Finally, we discuss learnability results on other classes of languages and provide examples for the case of languages over large alphabets. 
December 13, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Raycasting is a relatively simple and eyecatching technique underlying raytracing methods of rendering. Rendering is all about producing a visual representation of a 3D model. Because of the appeal of rendering and the geometry aspects of raycasting, the seventh talk of this series shall focus on the basic steps needed to create a visual representation of a 3D model, utilizing simple geometric tools, with the aim of implementing a library to perform the process. Beyond a fundamental implementation of a simple 3D model as a collection of faces (oriented triangles), details for the abstraction of a camera and an ambient light are also going to be discussed. 
December 6, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Reading binary data from a file is the epitome of manipulating geometric information. Expanding upon the subjects of the previous talk, the seventh talk of this series shall be devoted to completing the lowlevel process of reading and properly interpreting data from a binary STL file into a suitably created class, as a means of loading a representation of a 3D model into memory. By completing this significant task, functional aspects of the library can henceforth be tested on actual data. 
November 29, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Despite the possibility of creating extensive and largely efficient and manageable libraries relying solely on a small number of programming constructs, a number of programming language facilities have the potential to increase the appeal and readability of the code and decrease the usage complexity of the library, while assisting in the endeavour to achieve a certain level of "code elegance". In the sixth talk of this series, pointers, references and some other constructs, such as operator overloading, shall be extensively discussed and used, while expanding the library to cater for data input/output. In addition, some practical pieces of library functionality shall be briefly presented and elaborated upon as a "sneak peek" at the subject of the next couple of talks. 
November 22, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Programming is much more about writing source code and being familiar with the facilities provided by a programming language, along with the standard and, usually, a number of external libraries. Good programming practices improve productivity, facilitate maintainability, increase readability and maximize reusability of a library. The fifth talk of this series shall be concerned with the concept of using multiple files, including headers and sourcecode files, as a programming practice. At the same time, the accumulated information from previous talks will be used to put together a small library and use it to perform an individual task that lends itself to reuse. 
November 15, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Realworld information is stored in binary format within a storage medium. A number of standards underlie this format, which encode this binary information into a conceptually valid model. A formal data model serves the need of assigning meaning to blocks of information. This way, what is otherwise a large series of stored bits in order can be interpreted as the elements of a specific realworld entity, or an abstract counterpart thereof. The fourth talk of this series will focus on a brief description of data models and a commentary on their usefulness and necessity in programming. A small case of understanding and using an implemented data model in programming will be thoroughly walked through, with the purpose of reading data from an external binary file. 
November 8, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

A complex framework to solve problems of geometric nature consists of standalone abstractions, in the form of classes (or objects), which interact with each other in intricate ways. Instead of directly tackling problemsolving in a bruteforce coding approach, objectoriented programming caters for a much more fluent, intuitive and extensible functionality experience, at the expense of a higher level of coding omplexity. In the third talk of this series, the intricacies of objectoriented programming slowly emerge as implementation takes over the theoretical exposition of a conceptual object model consisting of fundamental geometric primitives. Transforming ideas in code shall be the central element of this talk, while striving to provide ample insight on complicated programming constructs through due persistence. 
November 1, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Applying any computational geometry algorithm on a real problem necessitates an abstraction of the problem itself.
An exhaustive abstract expression of the problem domain involves the identification and abstraction of all distinct
fundamental elements. In the second talk of the series, the fundamental geometric primitives shall be identified and corresponding abstractions are going to be implemented in an objectoriented manner in the programming language c++. At the same time, the objectoriented programming paradigm shall be presented on a needtoknow basis alongside the abstraction process. The procedure is expected to simultaneously serve the educational needs of acquaintance with the foundations of an objectoriented programming paradigm and the underlying language, as well as (one among various manifestations of) a methodological framework for computationally solving geometry problems in various areas of applied science. 
October 25, 11:00, Computers' Lab
Lowlevel Geometry Programming with C++ 

Subtle implementation issues abound in Computational Geometry.
In fact, it is a very long way from an empty module to a fullblown
library that performs anything even remotely useful and reliable in
terms of design or engineering. Undertaking this "trip" requires a
significant effort and fair awareness of the available resources,
especially when it coincides with the "trip" to learn efficient
coding. This talk is the first of an interactive presentation series
aiming to familiarize attendees with the multiplicity of aspects and
programming issues in the area of Computational Geometry, focusing on
the pragmatic perspective of a beginner programmer that starts from
scratch, putting together "dirty" code to illustrate principles of
software engineering. This first talk amounts to a motivational
introduction that touches upon the subject from the broader
perspectives of what Computational Geometry is from a practical
standpoint, how it assists in technological advancements and why
should Science students care about it at all, while striving to
maintain a delicately rigged balance between theory and practice in
evident favor of the latter. 
October 17, 13:00, Computers' Lab
Bayesian networks for regulatory network modelling and classification based on microarray data 

We introduce present Bayesian networks, a seminal class of probabilistic graphical
models for modelling dependence relationships between random variables, probabilistic
inference and causality under uncertainity. Due to their nature, Bayesian networks provide a versatile tool in
Bioinformatics for "reverseengineering" regulatory networks using expression data from
genes and/or proteins. 
May 24, 10:00, Computers' Lab
Weighted confoguration logic 

Master Thesis presentation. 
May 10 , 12:00, Computers' Lab
Image compression methods: 

One of the most frequently transferred type of information used nowadays is picture. From photographs uploaded to social media, to a hospital’s medical records, information needs to be saved and transferred as quickly and with the greatest precision possible. This leads an increasing amount of researchers to the study of image compression methods. The presentation consists of two parts, each describing a different image compression method, namely the SVD method and the JPEG Standard. For both algorithms, the mathematical background needed is explained. Next the methods are presented stepbystep and their results are demonstrated through a number of examples. 
An introduction to Matroids (slides) 

Matroids were introduced by Whitney in 1935 in an attempt to capture 
Neural networks: An application in medicine (slides) 

The device Kinect Sensor of Microsoft was developed and is being sold since 2010 originally as a game console. The last three years though, it is widely used for real time surveillance of humans either in their home or in a living lab aiming at the research on human’s motion. As a need of the surveillance, follows the development of flexible tools for recognizing and classifying people according to their skeleton’s data. In this survey 3 different types of Neural Networks are used, belonging to the powerful and fast growing field of machine learning, on a dataset that was collected for the purpose of the survey in the Living Lab of Medical Physics of AUTH. 
Complexity results related with Graph Searching and its Variants 

A common computational problem in graph theory is that of determining how many searchers are needed in order to search a graph while applying a sequence of moves. The moves are a) placing a searcher at a vertex, b) sliding a searcher along an edge, and, c) removing a searcher from a vertex. In this context, we are interested in finding the computational complexity of deciding whether k searchers are sufficient to search a graph G for a given integer k. Furthermore, we are looking for structural results one of which can be stated as finding the complete set of forbidden graphs that are minor minimal for graphs with a fixed search number. In this talk, we will give complexity theoretic and structural results related with graph searching and two of its variants: fast search and weighted search. 
Weighted Configuration Logic II 

In the second talk, we introduce our weighted configuration logic, and present the main results as well as several examples from real applications which motivate our work. 
Weighted Configuration Logic I 

In a two lectures' series, we intend to present our recent results on weighted configuration logic. In the first talk we introduce the audience to basic notions on configuration logic which models in a very sufficint way computer's architectures styles. 
Weighted tree automata in Approximate Description Logics (slides) 

Recently introduced problems in Description Logics (DLs) require the use of concept comparison measures. In this talk, we will briefly review these problems, show how concepts in the DL FL0 can be represented by infinite trees, and demonstrate how weighted automata working on aforementioned trees can be used to compute concept comparison measures. 
Biology in Computation: Evolving Intelligent Controllers  Combining Genetic Algorithms with Neural Networks (slides) 

Intelligent control is based on artificial intelligence constructs, or theories developed
to describe intelligent behavior, as demonstrated by living creatures. Most control trategies
require tactical choice of the parameters and controller characteristics, according to the
application. Intelligent control provides facilities of selfimprovement that automate the
process of choosing characteristics and parameters. One of these facilities is the oncept
of evolution, a central idea in Biology. 
Aperiodic Wang tile sets: Constructions and undecidability III (slides) 

In this short series of lectures, we will
introduce the notion of
Wang tiles, and we will present the classical constructions of
aperiodic Wang
tile sets, motivated by the ndecidability of the tiling problem,
and we will explain how these results form a link between dynamical
systems and theoretical
computer science. 
Aperiodic Wang tile sets: Constructions and undecidability II (cf. a relative paper) 

In this short series of lectures, we will
introduce the notion of
Wang tiles, and we will present the classical constructions of
aperiodic Wang
tile sets, motivated by the ndecidability of the tiling problem,
and we will explain how these results form a link between dynamical
systems and theoretical
computer science. 
Aperiodic Wang tile sets: Constructions and undecidability I (slides) 

In this short series of lectures, we will
introduce the notion of
Wang tiles, and we will present the classical constructions of
aperiodic Wang
tile sets, motivated by the ndecidability of the tiling problem,
and we will explain how these results form a link between dynamical
systems and theoretical
computer science. 
Minimization and hyperminimization of automata models 

Master Thesis presentation. 
Computational Complexity IV: PSPACE (slides) 

We introduce the notion of space complexity
and define the complexity classes PSPACE and PSPACEcomplete. Then we
present 3QSAT and Generalized Geography as two examples of space
complexity. 
Computational Complexity III: NP and computational intractability (slides) 

We introduce the notion of time complexity. We define the complexity classes P, NP and NPcomplete.
Then we present some computational problems and give an insight into
understanding the polynomial time reduction from one problem to
another. 
Computational Complexity II: Asymptotic notation and classification algorithms (slides) 

This talk is concerned with providing an
insight into understanding algorithms. We define worst, average and
best case of an algorithm and introduce the basic asymptotic notations
Big  Oh, Big  Omega and Big  Theta. Then we present some
classses of algorithms, more precisely specifically bruteforce, divide
and conquer, dynamic programming and randomized algorithms. 
Computational Complexity I: From finite automata to Turing machines (slides) 

This is the first talk, in a series of
lectures on fundamental notions on Computational Complexity. We recall
the models of finite automata and contextfree grammars, and introduce
the general computational model of Turing machines. Moreover, we refer
to computable as well as decidable problems. 
Singular curves over finite fields 


Skolem's Problem  A Challenge for Decidability (slides) 

In 1934, Norwegian mathematician Thoralf
Skolem, better known from his results in mathematical logic, proved
that the zero set of a linear recurrent sequence over integers is a
union of a finite set and finitely many arithmetic progressions. Later
research has discovered that the finitely many periodic sets (i.e. a
semilinear set) can be effectively constructed when the recurrence
relation is given. However, characterization of the aforesaid finite
set remains a longstanding open problem, and after more than 80 years
of Skolem's result we do not know the decidability status of the
following question: Given a linearly recurrent sequence over integers,
does there exist a zero in the sequence. In this talk, I will give an
overview of the problem and the recent progress on it. 
Kleene's Theorem implies Schützenberger's Theorem: 

We present an alternative proof, due to Dietrich Kuske, of the fundamental theorem of Schützenberger. More precisely, we show that the theorem of Schützenberger can be derived by the folklore Kleene's theorem. 
Hierarchy and Expansiveness in TwoDimensional Subshifts 

Using a deterministic version of the
selfsimilar method for constructing 2dimensional subshifts of finite
type (SFTs), we construct aperiodic 2D SFTs with a unique direction of
nonexpansiveness (extremely expansive) and prove that the emptiness
problem of SFTs is undecidable even for extremely expansive SFTs. As an
additional application of our method, we characterize the sets of
directions that can be the set of nonexpansive directions of 2D SFTs. 
Lattices and applications to cryptanalysis I 


20 years of PageRank (slides) 

We will explain the principles and the mathematics behind Google's PageRank algorithm, invented 20 years ago, with an emphasis on the construction of the Google matrix. We will furnish a completely worked out example of PageRank computation on a small network of 15 nodes, in order to exemplify the computational issues that underlie the algorithm and pinpoint scalability issues related to the actual Google matrix. 
Approximate Unification in Description Logics 

This talk presents the course of solving the
problem of Approximate Unification in Description Logics. After some
preliminaries on Description Logics and the (classical) problem of
Unification, we will introduce an approximate version of the problem.
In order to derive a solution several tools from other areas of
mathematics are needed, namely language equations, finite automata on
trees, Banach’s fixed point theorem and linear programming. 
Algebraic characterizations of recognizable formal power series (slides) 

We present two algebraic characterizations of recognizable formal power series, namely by matrices, and syntactic algebras. 
Infinite alphabtes and automata (slides) 

The aim of the presentation is an introduction to infinite alphabets and the basic automata models over infinite alphabets. We present the concept of data words and data languages and two equivalent models over these words, namely data automata and classmemory automata. Moreover, we mention finitememory automata and variable automata. Several results on closure properties and decidability problems will be discussed. 
We present an algebraic characterization of recognizable languages using the notion of syntactic monoids. 
Application of weighted finite automata to digital image compression (slides) 

We present the contribution of weigthed finite automata to the compression of digital images. A comparison of known protocols for digital image compression and the ones based on weighted finite automata is given. 
Contextfree grammars and algebraic systems of equations (notes, slides) 

We recall the concept of contextfree grammars and relate it to systems of algebraic equations. We show that the language generated by a contextfree grammar is a component of the least solution of the aforementioned system. Furthermore, we investigate whether the system of the grammar has a unigue solution. 
Formatted Text Input/Output with C++ (slides) 

The presentation encompasses the subject of performing input/ouput operations on formatted text data.
The inner representation of formatted text is discussed, with corresponding references to ASCII and
Unicode formats. Streams are explained and simple input/output boilerplate code is given. The fundamental
standard library routines of C and C++ are juxtaposed and contrasted. Emphasis is given on how C++ routines present themselves as highlevel, but are still lowlevel "behind the curtains" as there simply is no other way. The process of converting alphanumeric strings to actual numbers on input, and numbers to alphanumeric strings on output. The stringstream class is briefly presented and commented. Formatted text data input and output is a staple procedure in all interactive software. The accompanying practice and demonstrations in C++ evolves around simple formatted text input and output from local files. Some of the various idioms for conversions between numerical strings and actual numbers are presented. The general focus is put on inputting and outputting text from/to files, one line at a time. 
Basic Windows Programming with C++  The Win32 API (slides) 

The presentation is concerned with providing a beginning insight into creating applications utilizing
the facilities of Windows Operating System. Few basic structures of the Win32 API are presented, and
the Message Loop is explained. The concept of Callback Functions is demonstrated and its relation to
eventdriven programming is highlighted. The applications on Windows are merely windows populated with
controls that offer specific functionality. The presentation is accompanied by a small quiz, in order
to clarify a few delicate points of various C++ elements and concepts. The accompanying practice and demonstrations in C++ evolves around creating a Windows Application, made up of a basic window and a few controls. The usage of the Win32 API is demonstrated and the fundamental structures, functions and parameters are explained. 
ABI & API  Developing and Using a Static Library with C++ (slides) 

The presentation summarizes a few of the elements of application intercommunication at a lowlevel
and at a highlevel. Lowlevel intercommunication is mediated by studying the Binary Interface of an
Application. Whenever interaction is required with the application, for example an operating system,
the binary interface guides the developer on what to "send" and how, and what is "responded" by the
application. At a higher level, the Programming Interface of an Application exposes the functionality of the application itself in as simple a manner, as an instruction manual. The accompanying practice and demonstrations in C++ evolves around building a small standalone, static library. The library is a way to compact, pack and hide general functionality in a file or group of files (a static library is machine code), and include it in a project whenever this functionality is required, without having to rewrite the original code, or reinclude it in extra source code files. 
ObjectOriented Programming: Data Abstraction in C++ (slides) 

The presentation is an attempted concentration of a very influencing programming paradigm, that of
objectoriented programming. Data abstraction is the predominant concept, by means of which
elements of the realworld are simulated by theoretical programming objects called classes.
Characteristics (properties) and behavior are interwoven in class definitions, acting as prototypes
for creating class instances (objects). Objects with functionality hide their intricate behavior
details behind the simple names of their functions. Using welldesigned classes, program functionality is mediated through interactions between objects put together within a main function framework. The accompanying practice and demonstrations in C++ evolves around creating a small set of classes to build a simplistic library for creating 2D Arrays with elements and performing arithmetic operations with them. 
Bits and Bytes: Data, Memory and Pointers in Programming with C++ (slides) 

The presentation focuses on a number of elements of computer architecture. In specific, how
processors manipulate data and communicate with memory. The distinction is made between a
programming language's and the operating system's take on memory management. The general way
of storing memory in files is presented, clarifying the notion of byte endianness. Address spaces
and virtual memory management are briefly discussed.

Weighted variable automata over infinite alphabets 

We introduce weighted variable automata over infinite alphabets and commutative and idempotent semirings. We prove that the class of their behaviors is closed under sum, and under scalar, Hadamard, Cauchy, and shuffle product, as well as star operation. Furthermore, we consider rational and MSO definable series over infinite alphabets and we state a KleeneSchützenberger and a Büchi theorem. 
Decision and complexity
problems on small integer matrices (slides) 

Constructing elliptic curves using the complex multiplication method (in Greek) 

LTL vs CTL (Comparison and Practical Applications) (in Greek) 

Syntax and semantics of LTL and CTL will be presented, as well as several comparison results concerning practical applications. 
Digital image compression and weighted finite automata (in Greek) (slides) 

An introductory lecture on the compression of digital images with weighted finite automata protocols.

Automata over infinite alphabets 

An introductory lecture on the topic of automata whose inputs are finite words from infinite alphabets. The lecture will focus on the recently studied model of variable automata, presenting also some new results obtained by the local group on Theoretical Computer Science.

Contribution of automata to model checking (in Greek) 

An introductory lecture on model checking and the contribution of automata and LTL. 
DNA Computing: The first experiment of L. Adleman (in Greek) (slides) 

An introductory lecture on the field of DNA computing and a detailed description of the first experiment of Leonard Adleman. 
Quaternions, spatial Pythagorean hodographs, and rotations in R^3 and R^4 

Quaternions, the first example of a noncommutative algebra, arose as a byproduct of Hamilton's failed attempt to construct an "algebra of triples". Hamilton envisaged the quaternions as the "new language" of science and technology, but their place was usurped by vector analysis, an algebraically crude and overtly pragmatic subset of the quaternion algebra. A simple quaternion expression generates Pythagorean quadruples of polynomials, yielding an elegant rotationinvariant characterization of Pythagorean hodographs in R^3. Quaternions provide compact, intuitive descriptions for rotations in R^3, a fact that has generated renewed interest in them for applications in robotics, animation, computer graphics, and related fields. Quaternions also describe rotations in R^3 lading our geometric intuition from R^2 and R^3 to Euclidean spaces of higher dimension. 
Tree automata over infinite ranked alphabets  
We consider variable tree automata with infinite input ranked alphabets, a
model based on an underlying tree automaton that runs over a finite ranked
alphabet containing variable symbols. The underlying tree automaton computes
its tree language, and then replaces the variable symbols with symbols from
the infinite alphabet following certain rules. We show that the class of
recognizable tree languages over infinite ranked alphabets is closed under
union and intersection but not under complementation. Moreover, we show that 
An introduction to sequential functions  
Sequential functions are, in a sense, the simplest computable functions. There are especially interesting for hardware designers, since they are easily implemented on circuits. I will recall the definition of sequential automata, present several examples (addition, cut and replace, division by a fixed integer, coding, etc.) and explain the little known minimisation algorithm. I will also state, without proof, a nice characterization of these functions. 