Seminar on Theoretical Computer Science

and Discrete Mathematics

(directed by D. Poulakis and G. Rahonis)





April 24, 12:30, Computers' Lab


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


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


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

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

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

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

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

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

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

  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


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.