Efficient Algorithms, Automata and Data Structures

The annual workshop of the project APVV-15-0091

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

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.

Slovakia

Participants

Invited Speakers

Institute of Discrete Mathematics and Algebra

Bergakademie Freiberg

Freiberg, Germany

Department of Operations Research

Eötvös Loránd University

Budapest, Hungary

Faculty of Electrical Engineering and Computer Science

University of Maribor

Maribor,
Slovenia

Institute of Economics

Hungarian Academy of Sciences

Budapest, Hungary

Institute for Logic, Language & Computation

University of Amsterdam

Amsterdam, The Netherlands

Department of Operations Research and Actuarial Sciences

Corvinus University of Budapest

Budapest,
Hungary

Department of Computer Science

University of Bucharest

Bucharest,
Romania

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.

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.

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.

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.

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.

Given a graph *H*, the *k*-colored Gallai-Ramsey number
*gr _{k}(K_{3} : H)* is defined to be the minimum integer

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.

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
2^{n} for complementation.

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.

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.

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.

Let *H* be an arbitrary graph with vertex set *V(H)=[n _{H}]={1,...,n_{H}}*.
The

- u
_{t}= v_{t}, for t>h, - u
_{h}≠ v_{h}and u_{h}v_{h}∊ E(H), and - u
_{t}= v_{h}and v_{t}= u_{h}for t<h.

If *H* is isomorphic to a complete graph *K _{t}*, then we
speak of the Sierpiński graph

This is a joint work with Wilfried Imrich.

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.

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.

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.

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.

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

Slovakia