About Workshop

The workshop is organized as a part of the project Efficient algorithms, automata and data structures (APVV-15-0091). The mail goal of the workshop is to present current research results of the project team and to learn about the newest trends in research areas related to the project thanks to invited international speakers.

The main topics of the workshop EAADS 2017:

  • Algorithms on graphs (matchings, networks, colorings)
  • State and descriptional complexity
  • Formal concept analysis

About Project

The aim of the project is the research in the area of efficient algorithms for finite state automata, graph invariants and data analysis. More precisely, the goals are to obtain tighter bound for the state complexity of the conversion between various types of automata and devices with bounded stack, precise complexity of regular operations in binary and unary case, a detailed description of various complexity aspects of generalized graph invariants like vertex cover, independent set, maximum matching, that have applications in cryptography, medicine, organization of education and health care, image analysis and segmentation etc., better understanding of concept hierarchy in formal concept analysis and efficient algorithms for finding bonds between fuzzy contexts.

The project is supported by The Slovak Research and Development Agency.

3 days



Invited Speakers

Invited Speakers

Ingo Schiermeyer

Ingo Schiermeyer

Institute of Discrete Mathematics and Algebra
Bergakademie Freiberg
Freiberg, Germany

Tamás Fleiner

Tamás Fleiner

Department of Operations Research
Eötvös Loránd University
Budapest, Hungary

Iztok Peterin

Iztok Peterin

Faculty of Electrical Engineering and Computer Science
University of Maribor
Maribor, Slovenia

Péter Biró

Péter Biró

Institute of Economics
Hungarian Academy of Sciences
Budapest, Hungary

Ronald de Haan

Ronald de Haan

Institute for Logic, Language & Computation
University of Amsterdam
Amsterdam, The Netherlands

Zsuzsi Jankó

Zsuzsi Jankó

Department of Operations Research and Actuarial Sciences
Corvinus University of Budapest
Budapest, Hungary

Zsuzsi Jankó

Stefan Popescu

Department of Computer Science
University of Bucharest
Bucharest, Romania

Discussions and Collaboration

During the workshop there will be plenty of space for active collaboration and discussions about research topics and problems related to topics of the project.


Tuesday - morning session

09:00-09:30 (room: SJ1Z17T/VKM)

Ľubomír Antoni: Relationship between fuzzy subsets and Galois connections

We present the one-to-one correspondence between the set of all fuzzy subsets and the set of all Galois connections. The essential correspondences are built with the help of a-cuts, which represent fuzzy subsets by classical sets. Moreover, we present a relationship between strong fuzzy negations in the lattices and Galois connections. The various extensions of fuzzy subsets from the point of view of nestedness and negations are recalled. Joint work with Stanislav Krajči and Ondrej Krídlo.

09:30-10:00 (room: SJ1Z17T/VKM)

Miroslav Opiela: Indoor localization using Bayesian filtering

The indoor localization problem is considered to be a time-sequential, non-linear and non-Gaussian state estimation problem. Bayesian filtering is the commonly used stochastic filtering techique for the indoor positioning, where the current state of a system is computed from its previous state based on observations (in this case obtained from the smartphone sensors).
Under some assumption, Kalman filter and grid-based method provide the optimal solution for the posterior probability density computation. In other cases, including indoor positioning, Kalman filter, particle filter and grid-based method only approximate the posterior density. We will explain these Bayes filters when applied on the indoor positioning problem and provide evaluation results for the grid-based approach focusing on the influence of using the discrete filter and the localization accuracy for different grid types and step length estimations.

10:15-10:45 (room: SJ1Z17T/VKM)

Csaba Török: New computational models for interpolating cubic splines

We present two computational models for cubic splines. The first one is connected with the computation of unknown derivatives for interpolation splines. Based on new model equations for clamped cubic splines we derived reduced tridiagonal systems with richer right sides. The new standard linear systems are two, four, eight … times smaller than the original full system and they result in faster computational schemes in both sequential and parallel regime. The second computational model presents a new explicit form for interpolation splines. We show how to derive explicit formulas for cubic interpolating B-splines and Hermite splines of class C1 for both uniform and nonuniform grids. Thanks to the explicit interpolating formula new LS smoothing models can be constructed. Their advantage is in much easier interpretable coefficients than the control points of the B-splines. The smoothing is demonstrated on real data.

10:45-11:15 (room: SJ1Z17T/VKM)

Ondrej Krídlo: An adjoint pair for intuitionistic L-fuzzy values

We continue our prospective study of the generalization of formal concept analysis in terms of intuitionistic L-fuzzy sets. The main contribution here is an adjoint pair in the set of intuitionistic L-fuzzy values associated to a complete residuated lattice, which allows the definition of a pair of derivation operators which form an antitone Galois connection.

Tuesday - afternoon session

14:00-15:00 (room: SJ1Z17T/VKM)

Ingo Schiermeyer: Gallai-Ramsey numbers

Given a graph H, the k-colored Gallai-Ramsey number grk(K3 : H) is defined to be the minimum integer n such that every k-coloring (using all k colors) of the complete graph on n vertices contains either a rainbow triangle or a monochromatic copy of H. We will give an introduction to Ramsey numbers and Gallai-Ramsey numbers first. Then we will present Gallai-Ramsey numbers for several graphs H such as paths, cycles and complete graphs.

15:00-16:00 (room: SJ1Z17T/VKM)

Tamás Fleiner: List colorings with restricted lists

We prove an extension of Galvin's theorem, namely we show that any graph is χ-edge-choosable if no odd cycle has a common colour in the lists of its edges.

Wednesday - morning session

09:00-09:30 (room: SJ1Z17T/VKM)

Peter Mlynárčik: Nondeterministic complexity of operations on free and convex languages

We study the nondeterministic state complexity of basic regular operations on the classes of prefix-, suffix-, factor-, and subword-free and -convex regular languages. For the operations of union, intersection, complementation, concatenation, square, star, and reversal, we get the tight upper bounds for all considered classes except for complementation on factor- and subword-convex languages. Most of our witnesses are described over optimal alphabets. The most interesting result is the describing of a proper suffix-convex language over a five-letter alphabet meeting the upper bound 2n for complementation.

09:30-10:00 (room: SJ1Z17T/VKM)

Viliam Geffert: Languages in alternating O(loglog n) space

We shall present some new simulations for ASpace(loglog n), the class of languages accepted by alternating Turing machines with O(loglog n) space and their consequences for higher complexity classes. We shall also present solutions of some open problems and some problems related to ASpace(loglog n) not solved yet.

10:30-11:30 (room: SJ1Z17T/VKM)

Stefan Popescu: A survey on networks of polarized evolutionary processors

We consider a bio-inspired computing model: namely a variant of networks of evolutionary processors, where each processor and the data navigating through the network are considered to be polarized. While the polarity of the processors is predefined, the polarity of each string is dynamically computed, allowing the flow of the data through the network. We give examples on how this computing model can be used to solve NP-Complete problems. We show that tag systems can be simulated by these networks with a constant number of nodes, while Turing machines can be efficiently simulated by these networks with the number of nodes depending linearly on the tape alphabet of the Turing machine. We also propose two different ideas on how to simulate a non-deterministic Turing machine using a network with a constant number of nodes, but at a loss in time complexity.

11:30-12:00 (room: SJ1Z17T/VKM)

Galina Jirásková: On the descriptional complexity of the forever operator

Motivated by restricted temporal logic, the forever (=not eventually not) operator has been investigated by Jean-Camille Birget in 1996. He obtained the upper and lower bounds on the nondeterministic state complexity of this operator. We improve this result and get the exact nondeterministic complexity. We also study different trade-offs for this operator: Assuming that an operand is given by deterministic, partial deterministic, nondeterministic, nondeterministic with multiple initial states, alternating, or boolean finite automaton, we ask how many states are sufficient and necessary in the worst case for an automaton of one of this six models to accept the result of the forever operator. We get the exact trade-offs in 32 out of 36 cases. One of the most interesting results is the NFA-to-DFA trade-off given by Dedekind number which counts the number of antichains of subsets of a finite set.

Wednesday - afternoon session

13:00-13:45 (room: SJ1Z17T/VKM)

Iztok Peterin: Recognizing generalized Sierpiński graphs

Let H be an arbitrary graph with vertex set V(H)=[nH]={1,...,nH}. The generalized Sierpiński graph SHn, n ∊ N, is defined on the vertex set [nH]n, two different vertices u =un ... u1 and v = vn...v1 being adjacent if and only if there exists an h ∊ [n] such that

  • ut = vt, for t>h,
  • uh ≠ vh and uhvh ∊ E(H), and
  • ut = vh and vt = uh for t<h.

If H is isomorphic to a complete graph Kt, then we speak of the Sierpiński graph SKtn. We present an algorithm that recognizes Sierpiński graphs SKtn in O(|V(SKtn)|1+1/n) time. A polynomial time algorithm is given for generalized Sierpiński graphs when H belong to a certain graph class. We also describe how to derive a base graph H from an arbitrary SHn.
This is a joint work with Wilfried Imrich.

13:45-14:30 (room: SJ1Z17T/VKM)

Zsuzsi Jankó: Trading networks with bilateral contracts

We consider general networks of bilateral contracts that include supply chains. We define a new stability concept, called trail stability, and show that any network of bilateral contracts has a trail- stable outcome whenever agents' choice functions satisfy full substitutability. Trail stability is a natural extension of chain stability, but is a stronger solution concept in general contract networks. Trail-stable outcomes are not immune to deviations of arbitrary sets of firms. We show that trail-stable outcomes always exist, For trail- stable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategy-proofness and comparative statics of firm entry and exit. We then describe the relationships between various other concepts.
Joint work with Tamás Fleiner, Alexander Teytelboym and Akihisa Tamura.

15:00-15:45 (room: SJ1Z17T/VKM)

Ronald de Haan: Pareto optimal allocation under uncertain preferences

The assignment problem is one of the most well-studied settings in social choice, matching, and discrete allocation. We consider this problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under two natural uncertainty models: (1) the lottery model in which each agent has an independent probability distribution over linear orders and (2) the joint probability model that involves a joint probability distribution over preference profiles. For both of these models, we present a number of algorithmic and complexity results highlighting the difference and similarities in the complexity of the two models.
Joint work with Haris Aziz and Baharak Rastegari.

15:45-16:15 (room: SJ1Z17T/VKM)

Gabriel Semanišin: Recent progress in k-path vertex cover problem

A subset of the vertex set of a graph G is called k-Path Vertex Cover Set if it intersects all path of order k in G. This concept was introduced by 2011 by B. Brešar, F. Kardoš, J. Katrenič and G. Semanišin as a generalisation of the well known Vertex Cover Problem. The concept became quite atractive and was investigated by many authors. In our contribution we summarise recent develepment in this area.

Thursday - morning session

9:30-10:30 (room: SJ1Z17T/VKM)

Katarína Cechlárová: Fair division of a graph

We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases where the underlying graph has simple structure, and/or the number of agents-or, less restrictively, the number of agent types-is small. In particular, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently. In the second part of the talk we deal with the situation when the items are undesirable.

10:45-11:45 (room: SJ1Z17T/VKM)

Péter Biró: Stable matching with uncertain preferences

We study the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. The talk will be based on two papers. In the first, we consider three models of uncertainty: (1) lottery model — in which for each agent, there is a probability distribution over linear preferences, (2) compact indifference model — for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model — there is a lottery over preference profiles. In the second paper we consider (4) pairwise preferences - in which the agents have probabilistic pairwise comparisons over their possible partners that may be intransitive. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant. Joint work with Haris Aziz, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari.


Institute of Computer Science
Faculty of Science
P. J. Šafárik University in Košice

Jesenná 5
040 01 Košice