Seminar on Theoretical Computer Science

and Discrete Mathematics

(directed by D. Poulakis and G. Rahonis)

 
2022

 

March 2, 19:00

zoom link:
https://authgr.zoom.us/j/98356355377?pwd=RUNsV1Z6S3d1bGU5ZFBUeUZXdlQyZz09
Meeting ID: 983 5635 5377
Passcode: 392455

 

Cryptography in the Post-Quantum Era (slides)

 

In this talk, we start by introducing the audience to the fundamentals of Cryptography and Quantum Computing in order to break down the science behind the so-called “Quantum Threat” to Cryptography. Then, we continue by stating a way we can face this threat with, Post-Quantum Cryptography, which we further analyze by presenting two families of cryptographic schemes and systems that are a part of it, Hash-based Cryptography and Code-based Cryptography. In closing, we conclude by giving insight into existent and future plans and operations of some federal agencies that actively work towards countering the quantum threat, in order to gain a global perspective of the subject.

 

 

 

2021

 

December 16, 19:00

zoom link:
https://authgr.zoom.us/j/98356355377?pwd=RUNsV1Z6S3d1bGU5ZFBUeUZXdlQyZz09
Meeting ID: 983 5635 5377
Passcode: 392455

 

The contribution of new technologies in the diagnosis and treatment of Parkinson's disease: The i-PROGNOSIS project (slides)

 

Parkinson’s Disease (PD) is a progressive disease that is caused mainly by the loss of brain cells responsible for the production of a brain chemical, called dopamine. Varying symptoms are experienced by patients and do not include only the common tremor and other motor symptoms. In fact, the early ones are constipation, reduced ability to smell, sleep problems, depression and pain. No definite early detection laboratory tests have been established for Parkinson’s and the very early symptoms are often missed. No cure has been found to reverse Parkinson’s disease. Patients usually receive medication to minimise motor symptoms and manage symptoms not related to movement.

Based on this evidence, new technologies and ICT-based solutions are rapidly proliferating towards the development of novel digital biomarkers for unobtrusive early PD symptoms identification and assessment. In the same context, ICT-based solutions are emerging for assisting PD patients’ in their daily routines and sustaining their quality of life over the course of the disease. The i-PROGNOSIS project, funded under the Horizon 2020 program of EU, by employing the latest technologies and sourcing data from people, built early PD detection and assessment biomarkers and designed cutting-edge interventions for assisting PD patients.

 

December 15, 19:00

zoom link:
https://authgr.zoom.us/j/98356355377?pwd=RUNsV1Z6S3d1bGU5ZFBUeUZXdlQyZz09
Meeting ID: 983 5635 5377
Passcode: 392455

 

Digital Transformation as Gamechanger for growth (talk video)

   

 

 

December 8, 18:45

zoom link:
https://authgr.zoom.us/j/98356355377?pwd=RUNsV1Z6S3d1bGU5ZFBUeUZXdlQyZz09
Meeting ID: 983 5635 5377
Passcode: 392455

 

Extended Propositional Interaction Logic: Modelling order restrictions in
architectures of component-based systems (slides)

 

Well-founded design is a key principle for large and complex systems in order to ensure correctness by construction. Rigorous methods are mainly component-based, where modelling is performed by assembling and coordinating multiple components. Coordination principles can be described by architectures that characterize the permissible interactions and define the topology of the components. Recently, architectures have been formalized by means of logics. Although existing logics, describe nicely several architectures, they do not consider an important feature: the specified order required for the execution of the interactions. Several architectures found in applications, including Publish/Subscribe and Request/Response, impose such restrictions on the execution of the interactions. In this talk, we present a propositional logic, namely, Extended Propositional Interaction Logic, which is proved sufficient for modelling the order restrictions in the permissible interactions of architectures. Moreover, our logic encodes recursive interactions which in turn allows to describe the subsequent implementation of an architecture during the system's operation. Furthermore, we present examples of formulas of our logic for describing well-known architectures.

December 1, 19:00

zoom link:
https://authgr.zoom.us/j/98356355377?pwd=RUNsV1Z6S3d1bGU5ZFBUeUZXdlQyZz09
Meeting ID: 983 5635 5377
Passcode: 392455

 

Algebraic Properties of Connectors in Weighted Architectures (slides)

 

We present a strict mathematical theory for connectors, with quantitative features, involved in component-based systems. We state the motivation of our work by exposing the contribution of weighted connectors in concrete examples of inportant software architectures.

 
2020

 

March 4, 11:45, Computers' Lab

 

Logical directed description of software architectures with
quantitative features (slides)

 

Propositional configuration logic describes qualitative characteristics of software architectures. Though, several practical applications require representation of quantitative characteristics. For instance, in Publish/Subscribe architecture it is important to express the priorities with which a subscriber receives  messages from  topics. In this talk we introduce a weighted propositional configuration logic and present formulas of that logic describing architectures with quantitative characteristics. Furthermore, we show decidability results of our logic.

 

February 26, 11:30, Computers' Lab

 

Logical directed description of software architectures (slides)

 

Architecture is a critical issue in design and development of complex software systems. If the construction of a software system is based on a "good" architecture, then the system satisfies most of its functional and quality requirements.
In this talk, we introduce a logic which describes, in a strict mathematical way, most of the well-known architectures. We present several examples of architectures, and show the decidability of equivalence of formulas of that logic.

 

 
2019

 

July 4, 10:30, Computers' Lab

 

Variations of nondeterminism using the example
of alternating automata (slides)

 

Nondeterministic transitions in Turing machines, pushdown automata, or finite automata are all interpreted in the same way: existentially. An input is accepted if there exists an accepting computation.
In this talk I want to highlight that this definition is not necessary and investigate an alternative: alternation. I will present the basic model of alternating automata, interesting results about their expressive power, as well as generalizations such as weighted alternating automata.

 

June 5, 12:30, Computers' Lab

 

Automata over infinite words (slides in Greek )

 

An intoductory lecture on automata over infinite words: Definitions. Closure properties of the class their behaviors. The determinization problem.

 

May 22, 10:00, Computers' Lab

 

Weighted variable automata over infinite words with discounting (slides)

 

We introduce weighted variable Buchi automata with discounting over infinite alphabets and the max-plus semiring. We prove that the class of their behaviors is closed under max, scalar sum, Hadamard sum, d-Cauchy sum and d-ω-iteration. We introduce also weighted variable Muller automata with discounting over infinte alphabets and the max-plus semiring and show their expressive equivalence to weighted variable Buchi automata with discounting. Then we consider rational series over infinite words and
infinite alphabets with discounting and state a Kleene-Schutzenberger type theorem. Finally, we obtain an d-ω-WVMSO logical characterization for the class of series accepted by weighted variable Buchi automata with discounting.

 

May 14, 13:00, Room M2

In collaboration with
Laboratory of Statistics, Chaos, and Stochastic Analysis
Director: G. Tsaklidis

 

An introduction to Dynamical systems, chaos and their applications
(slides in Greek )

 
Dynamical systems describe a wide spectrum of natural and artificial systems, from physics and biology to medicine, engineering, economics and more. The emergence of chaotic behavior is one of the most interesting aspects of the analysis of dynamical systems, with numerous applications in the aforementioned fields. In this introductory lecture, we will discuss dynamical systems, chaos and its various trending applications.

February 27, 11:00, Computers' Lab

 

An introduction to DNA computing (slides in Greek )

 

An introductory lecture on the field of DNA computing, Leonard Adleman's first experiment, the largest problem solved without electronic devices and the use of Formal Language Theory on the theoretical analysis of DNA Computing.

 

 

2018

 

December 19, 11:30, Computers' Lab

 

A formal framework for multi-view modeling and the multi-view consistency problem (slides)

 

Model-based design of complex systems involves several stakeholders that derive distinct, but yet related, models for the systems. Then, a crucial issue is to ensure consistency among the models, i.e., that they do not contradict each other.

In this presentation we introduce the multi-view modeling technique and one of its basic problems, namely, the multi-view consistency problem. We present a formal framework for the topic, including a generic algorithm for checking view consistency. Moreover, we provide an instantiation of the algorithm for Büchi automata views obtained by periodic sampling.

 

December 12, 10:00, Computers' Lab

 

Computational Complexity ΙΙΙ: Limits of Computation (slides)

 
In the last talk, we introduce the notions of time and space complexity. We define the complexity classes P, NP, NP-complete, PSPACE and PSPACE-complete. We give examples of problems that belong to these classes. We give furthermore an insight into understanding the polynomial time reduction from one problem to another.

 

December 5, 10:30, Computers' Lab

 

Computational Complexity II: Introduction to Algorithms (slides)

  In this talk, we focus on algorithms. We introduce the basic asymptotic notations Big-Oh, Big-Omega and Big-Theta. Asymptotic notation are used to compare algorithms according to their efficiency. Then we present some classes of algorithms and apply them to solve the sorting problem.

 

November 28, 10:00, Computers' Lab

 

Computational Complexity I: Computability vs Complexity (slides)

 

In a series of three lectures, we will look at some concepts from the classical theory of computation. In the first one we recall the models of finite automata and context-free grammars, and introduce Turing machines.


 

October 30, 11:15, Computers' Lab

 

Weighted Automata and Netwotks (slides)

 

Weighted finite automata are classical nondeterministic automata in which the transitions carry weights. These weights may model, e.g., the amount of resources needed for the execution of a transition, the probability or reliability of its successful execution. The weights often form the algebraic structure of a semiring, but more recently, some more general algebraic structures are also used. When the weights are taken from a suitable ordered algebraic structure and are interpreted as truth values, we talk about multi-valued or fuzzy automata.

I will present some new results concerning the fundamental problems of the theory of weighted automata – state reduction and equivalence testing. These problems are reduced to the problems of solving a particular system of matrix inequations, and we discuss conditions on the structure of the weights under which this system can be efficiently solved. Solving these systems is based on concepts of residuation or relative residuation on matrices, which are present, for instance, if the underlying semiring is additively idempotent or it is a unital quantale. The case when this semiring is a max-plus quantale or some related quantale is especially interesting.

I will also show that the methodology developed to solve the problems of state reduction and equivalence testing for weighted automata can be successfully applied in Social Network Analysis, more precisely in the positional analysis of weighted networks.



 

April 24, 12:30, Computers' Lab

 

Fundamental Problems of Fuzzy Automata Theory (slides)

 

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

 

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.  Martin-Lof'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 Martin-Lof's system, since a cyclic proof
system does not have to choose fixed induction formulas in advance. The equivalence of the provability of Martin-Lof'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 (slides)

  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.

 

 

2017

 

December 13, 11:00, Computers' Lab

 

Low-level Geometry Programming with C++
Part VIΙI: Rendering in 3D using Ray-Casting (slides)

  Ray-casting is a relatively simple and eye-catching technique underlying ray-tracing 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 ray-casting, 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

 

Low-level Geometry Programming with C++
Part VΙI: Language Subtleties and Technicalities Revisited (slides)

  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 low-level 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

 

Low-level Geometry Programming with C++
Part VI: Language Subtleties and Technicalities (slides)

  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

 

Low-level Geometry Programming with C++
Part V: Putting the Pieces Together (slides)

  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 source-code 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

 

Low-level Geometry Programming with C++
Part IV: Data Modelling and Input/Output (slides)

  Real-world 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 real-world 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

 

Low-level Geometry Programming with C++
Part III: Data Structure Implementation (slides)

  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 problem-solving in a brute-force coding approach, object-oriented 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 object-oriented 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

 

Low-level Geometry Programming with C++
Part II: Geometric Primitives and Basic Functionality (slides)

  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 object-oriented manner in the programming language c++. At the same time, the object-oriented programming paradigm shall be presented on a need-to-know basis alongside the abstraction process. The procedure is expected to simultaneously serve the educational needs of acquaintance with the foundations of an object-oriented 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

 

Low-level Geometry Programming with C++
Part I: A Motivational Introduction to Computational Geometry (lecture)

 

Subtle implementation issues abound in Computational Geometry. In fact, it is a very long way from an empty module to a full-blown 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 "reverse-engineering" regulatory networks using expression data from genes and/or proteins.
Bayesian networks can be used as classifiers in the statistical learning field for disease diagnosis from microarray data. We propose the Naive Bayes Classifier as a suitable predictor for the diagnosis and distinction of Adenocarcynoma and Mesothelioma based on gene expression Data from tumor samples.

 

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
(slides)

 

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.

 
 
2016

 

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)
(slides)

 

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.

 

2015

 

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.

 

 

2014

 

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.

 

2013
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.

 

2012
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.

 

2011
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.

 

2010
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.