(directed by D. Poulakis and G. Rahonis)
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. 