Seminar on Theoretical Computer Science

and Discrete Mathematics

(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:
i) Singular Value Decomposition (slides)
ii)The JPEG Standard


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 step-by-step and their results are demonstrated through a number of examples.


May 3 , 12:00, Computers' Lab

An introduction to Matroids (slides)


Matroids were introduced by Whitney in 1935 in an attempt to capture
abstractly the fundamental properties of dependence that are common to
graphs and matrices. Since then matroid theory has been an active area
of mathematics combining several different areas such as abstract and
linear algebra, geometry, combinatorics and graph theory. The importance of
matroid theory is revealed greatly by results which have profound
implications to combinatorial optimization such as Seymour's
decomposition theorem on regular matroids.


April 26, 13:00, Computers' Lab

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.


April 5, 13:00, Computers' Lab

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.


March 29, 11:30, Computers' Lab

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.


March 22, 11:30, Computers' Lab

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.

March 16, 15:00, Computers' Lab

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.

January 18, 10:00, Computers' Lab

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 self-improvement that automate the process of choosing characteristics and parameters. One of these facilities is the oncept of evolution, a central idea in Biology.
This presentation is an elaboration on the most fundamental elements of Neuroevolution, namely the use of genetic algorithms to evolve a population of neural networks adapted to performing a specific task. A simulation is also included, in order to stimulate interest and provide insight into the essence of the technique.



December 14, 11:45, Computers' Lab

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.
(III) The aperiodic tile set of Kari-Culik, Wang tiles as dynamical systems.

December 7, 11:00, Computers' Lab

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.
(II) The aperiodic tile set of Berger-Robinson, undecidability of the tiling problem.

November 30, 12:00, Computers' Lab

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.
(I) Wang tile sets, tiling problems, semi-decidability of periodic tiling prob lem, co-semidecidability of tiling problem, undecidability of the anchored tiling problem.


November 23, 11:00, Computers' Lab

Minimization and hyper-minimization of automata models


Master Thesis presentation.


November 16, 11:00, Computers' Lab

Computational Complexity IV: PSPACE (slides)


We introduce the notion of space complexity and define the complexity classes PSPACE and PSPACE-complete. Then we present 3-QSAT and Generalized Geography as two examples of space complexity.

November 9, 10:45, Computers' Lab

Computational Complexity III: NP and computational intractability (slides)


We introduce the notion of time complexity. We define the complexity classes P, NP and NP-complete. Then we present some computational problems and give an insight into understanding the polynomial time reduction from one problem to another.

November 2, 10:45, Computers' Lab

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 brute-force, divide and conquer, dynamic programming and randomized algorithms.


October 19, 11:00, Computers' Lab

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 context-free grammars, and introduce the general computational model of Turing machines. Moreover, we refer to computable as well as decidable problems.


June 23, 12:00, Computers' Lab

Singular curves over finite fields



May 18, 11:00, Computers' Lab

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 long-standing 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.

April 20, 12:15, Computers' Lab

Kleene's Theorem implies Schützenberger's Theorem:
A proof by Dietrich Kuske (slides)


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.


April 13, 11:00, Computers' Lab

Hierarchy and Expansiveness in Two-Dimensional Subshifts
of Finite Type


Using a deterministic version of the self-similar method for constructing 2-dimensional subshifts of finite type (SFTs), we construct aperiodic 2D SFTs with a unique direction of non-expansiveness (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 non-expansive directions of 2D SFTs.


April 5, 11:00, Room M2

Lattices and applications to cryptanalysis I



April 4, 12:00, Computers' Lab

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.

March 30, 11:00, Computers' Lab

Approximate Unification in Description Logics
(or how to use most of the Mathematics in one problem)


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.


March 23, 11:00, Computers' Lab

Algebraic characterizations of recognizable formal power series (slides)


We present two algebraic characterizations of recognizable formal power series, namely by matrices, and syntactic algebras.


March 16, 11:00, Computers' Lab

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 class-memory automata. Moreover, we mention finite-memory automata and variable automata. Several results on closure properties and decidability problems will be discussed.


Januray 13, 11:00, Computers' Lab

On the syntactic monoid of languages (notes, slides)


We present an algebraic characterization of recognizable languages using the notion of syntactic monoids.




December 16, 11:15, Computers' Lab

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.


December 2, 11:00, Computers' Lab

Context-free grammars and algebraic systems of equations (notes, slides)

  We recall the concept of context-free grammars and relate it to systems of algebraic equations. We show that the language generated by a context-free 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.


November 25, 11:00, Computers' Lab

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 high-level, but are still low-level "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.


November 18, 11:00, Computers' Lab

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 event-driven 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.


November 4, 11:00, Computers' Lab

ABI & API - Developing and Using a Static Library with C++ (slides)

  The presentation summarizes a few of the elements of application intercommunication at a low-level and at a high-level. Low-level 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 stand-alone, 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 re-include it in extra source code files.


October 21, 11:00, Computers' Lab

Object-Oriented Programming: Data Abstraction in C++ (slides)

  The presentation is an attempted concentration of a very influencing programming paradigm, that of object-oriented programming. Data abstraction is the predominant concept, by means of which elements of the real-world 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 well-designed 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.


October 14, 11:00, Computers' Lab

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.

The accompanying practice and demonstrations in C++ evolve around pointers and low-level memory management, culminating in how pointer-dependent context from C is thoroughly being hidden in C++ behind high-level constructs and techniques.





June 25, 10:00, Computers' Lab

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 Kleene-Schützenberger and a Büchi theorem.


May 14, 13:15, Computers' Lab

Decision and complexity problems on small integer matrices (slides)



March 26, 13:00, M2

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



March 19, 13:00, Computers' Lab

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.


January 15, 11:30, Computers' Lab

Digital image compression and weighted finite automata (in Greek) (slides)


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


December 11, 13:15, Computers' Lab

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.


December 4, 13:15, Computers' Lab

Contribution of automata to model checking (in Greek)

  An introductory lecture on model checking and the contribution of automata and LTL.


November 27, 13:15, Computers' Lab

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.


October 18, 11:00, M2

Quaternions, spatial Pythagorean hodographs, and rotations in R^3 and R^4


Quaternions, the first example of a non-commutative algebra, arose as a by-product 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 rotation-invariant 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.


December 21, 13:45, Computers' Lab
  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
the emptiness problem is decidable, and the equivalence and universality problems are decidable within special subclasses of variable tree automata.


October 20, 13:15, Room M2
  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.