The annual workshop of the project APVV-24-0103
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 2026:
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.
Department of Mathematics and Computing Science
Saint Mary's University
Halifax, Nova Scotia, Canada
Department of Software Science
Tallinn University of Technology
Tallinn, Estonia
Department of Mathematics
Faculty of Arts and Science
Eastern Mediterranean University
Famagusta, North Cyprus
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.
Consider a hard NFA problem like universality, or equivalence. We want a PTIME randomized test to give us information about the hard problem via sampling words from Σ*. Similarly, for a given hard Diophantine equation, we want to sample integers from N and test whether the equation has any solution. Typically, sampling relies on the uniform probability distribution, but there is no uniform distribution on N, or on Σ*. What is a good distribution D? How to sample from D in PTIME? Which hard problems have a good PRAX algorithm? The talk is based on recent and ongoing research with several colleagues.
Experience from redesigning the Formal Languages course at the Technical University of Košice, including practical assignments, model-driven software development, visualization tools, automation, and student feedback.
Related links:
Course webpage
Visualization tool
Overview of finite automata with multiple initial states, known results on state complexity and decision problems, new DFA conversion bounds, automata generation methods, and ongoing work on minimization and operations.
Atoms of regular languages were introduced in 2011 by Brzozowski and Tamm. The atoms of a regular language are non-empty intersections of uncomplemented or complemented left quotients of the language, where each quotient appears in a term of the intersection. Atoms of a regular language L can be considered as its building blocks, since any quotient of L, including L itself, is a disjoint union of atoms. Every regular language defines a unique NFA, the átomaton, whose states are the atoms of the language. Recently, several old results of automata theory have been revisited using atoms of regular languages: Brzozowski's double-reversal method for minimizing a DFA was generalized, the Kameda-Weiner method of finding a minimal NFA was reinterpreted in terms of atoms, and lower bound methods for the size of an NFA were presented in terms of quotients and atoms of regular languages. Also, atoms play an important role in Boolean automata (BFA). The size of a minimal BFA is directly related to the number of atoms of that language. It has been shown how to construct a minimal BFA using the atoms of a given language. In the talk, we review some results related to atoms.
TBA
Mathematical modeling serves as a powerful framework for uncovering the hidden structures and universal organizational principles embedded within language. This talk introduces the theoretical background of quantitative linguistics, demonstrating its utility through a series of foundational examples. Three pivotal linguistic laws will be critically discussed: Zipf’s law of word frequency, the Menzerath–Altmann law regarding the relationship between language constructs and their constituents, and the Piotrowski law concerning the mathematical dynamics of language change over time. While these models were originally conceptualized for natural human language, their application can be extended to a much broader comparative context, e.g., sign language, computer programming languages, DNA, and complex animal communication systems. We will address the question: are these mathematical regularities a unique byproduct of human cognition, or do they reflect universal, system-independent principles of efficient information processing and structural optimization?
Fractals are geometric objects that are self-similar, i.e., some parts of them resemble to the whole. We define automata such that their graphs have fractal structures. Consequently, each of these automata has infinitely many states, however, because of the self-similarity, their structure can be defined with a finite description. Fractal automata with one head, reading the input in traditional left-to-right manner, accept exactly the context-free languages. Specific variants of fractal automata accept exactly the deterministic context-free and the linear context-free languages. Fractal automata with two heads, reading and processing the input from its two extremes, are able to accept a class of mildly context-sensitive languages. Relations between (one- and two-head) fractal automata with (one- and two-head) pushdown automata, and to pushdown CD systems (of regular and linear grammars) are shown.
We investigate the state complexity of the boundary operation on the classes of prefix-, suffix-, factor-, and subword-free and closed languages, and on the classes of right, left, two-sided, and all-sided ideal languages. For each of these classes, we obtain a tight upper bound on the state complexity of boundary. To describe witness languages, we use a ternary alphabet in the prefix-free case, a quaternary alphabet in the suffix-free case, and a binary alphabet in the remaining free cases, a binary alphabet for prefix-closed languages, and a ternary alphabet for the remaining classes. We also show that these alphabets are optimal in the sense that the corresponding upper bounds cannot be met by languages defined over a smaller alphabet. In the binary case, we derive a lower bound smaller by two for suffix-closed languages, and a tight upper bound of n+1 for factor- and subword-closed languages. The state complexity of the boundary of unary closed languages is n. Hence, for all smaller alphabets, we establish the exact state complexity of the boundary operation on each considered class, except for binary suffix-closed languages. Since the boundary of a language coincides with that of its complement, and the complement of a closed language is an ideal language, all our results for closed languages extend to the classes of right, left, two-sided, and all-sided ideals. Consequently, we provide almost complete solution to the problem of establishing the state complexity of the boundary operation on all considered classes.
Institute of Computer Science
Faculty of Science
P. J. Šafárik University in Košice
Jesenná 5
040 01 Košice
Slovakia
