About Workshop
The workshop is organized as a part of the project Automata Models: Descriptional and Computational Complexity (APVV-24-0103).
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 2025:
- State and descriptional complexity
- Models of automata
- New approaches in automata theory
About Project
The main aim of the project is the basic research in the area of computational and descriptional
complexity of formal languages represented by different models of automata. These goals follow the
results of recently finished grant APVV-15-0091, a successful joint research project of the Institute
of Computer Science of Faculty of Science of P. J. Šafárik University and Mathematical Institute of
the Slovak Academy of Sciences. We expect that this cooperation will continue and hence formulated
goals will be attained. The results of this research can be effectively used in several areas of
mathematics and computer science and in various applications such as pattern matching, text pattern
recognition in large data files, detection of critical parts of codes, and similarity analysis of
DNA strands. This project aims to investigate operational complexity for some automata models
including the examination of ranges of all possible complexities, to solve problems related to binary
coded languages, and to get the computational complexity of decidability problems for subclasses of
regular and context-free languages. We intend to get exact values on operational complexity for
different automata models like, for example, two-way nondeterministic, unambiguous, alternating,
and Las Vegas finite automata, and multiple entry deterministic automata. Getting the results on
descriptional complexity of combined operations (multiple concatenation, star-complement-star, minimal
star basis, forever operator etc.) is our next goal. There is a genuine interest for these results in
the international research community. We plan to get the exact values of these complexities or at
least lower and upper bounds close to each other. Another classical topic is the magic number problem
where the focus is not only on the worst-case complexity but rather on the range of all possible
complexities. Our aim is to investigate this problem for several regular operations (square, cut,
left and right quotient, etc.) and its variant for accepting state complexity. From the natural
motivation of information being stored in binary format with specific properties at the lowest level
of abstraction, the state complexity of binary coded languages emerges as our next topic of interest.
We focus on three primary goals here. First, we are going to investigate structural similarities
between the deterministic finite automaton for the original language and the deterministic finite
automaton for the binary coded version of the same language. Second, given a deterministic finite
automaton for a regular language, we ask whether the optimal deterministic finite automaton for
its binary coded version can be constructed in polynomial time or the problem is NP-hard. Third,
e would like to know whether there exists a complete state hierarchy for all prefix binary codes.
Our next goal is to continue the research on subclasses of regular and context-free languages and
the relationships between them. We plan to obtain some more closure and decidability properties for
these subclasses. We expect to get decidability properties for subregular classes by describing
properties of languages in given subclasses with specific small transducers which are suitable to
represent relations between two strings. We are also especially interested in the subclasses of
context-free languages described by restricted models of deterministic biautomata which are closely
related to grammars used for designing parsers in compilers.
The project is supported by the Slovak Research and Development
Agency.
