19 citations · 55 across the 13 of their papers we have counts for
13 papers · 1 filter
Proceedings 17th International Conference on Automata and Formal Languages
Michal Hospodár, Galina Jirásková, Viktor Olejár +2
The 17th International Conference on Automata and Formal Languages (AFL 2026) was held in Košice, September 7-10, 2026. It was organized by the Faculty of Science, P. J. Šafárik Un…
State Complexity of Multiple Concatenation
Jozef Jirásek, Galina Jirásková
We describe witness languages meeting the upper bound on the state complexity of the multiple concatenation of regular languages over an alphabet of size with a significa…
Operations on Boolean and Alternating Finite Automata
Galina Jirásková
We examine the complexity of basic regular operations on languages represented by Boolean and alternating finite automata. We get tight upper bounds m+n and m+n+1 for union, inters…
On the State Complexity of the Shuffle of Regular Languages
Janusz Brzozowski, Galina Jirásková, Bo Liu +2
We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-…
Operations on Automata with All States Final
Kristína Čevorová, Galina Jirásková, Peter Mlynárčik +2
We study the complexity of basic regular operations on languages represented by incomplete deterministic or nondeterministic automata, in which all states are final. Such languages…
On Upper and Lower Bounds on the Length of Alternating Towers
Štěpán Holub, Galina Jirásková, Tomáš Masopust
A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the ot…
On the State Complexity of the Reverse of R- and J-trivial Regular Languages
Galina Jirásková, Tomáš Masopust
The tight upper bound on the state complexity of the reverse of R-trivial and J-trivial regular languages of the state complexity n is 2^{n-1}. The witness is ternary for R-trivial…
The state complexity of star-complement-star
Galina Jiraskova, Jeffrey Shallit
We resolve an open question by determining matching (asymptotic) upper and lower bounds on the state complexity of the operation that sends a language L to (c(L*))*, where c() deno…
Complexity in Prefix-Free Regular Languages
Galina Jirásková, Monika Krausová
We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over s…
Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages
Janusz Brzozowski, Galina Jirásková, Baiyu Li +1
A language L is prefix-free if, whenever words u and v are in L and u is a prefix of v, then u=v. Suffix-, factor-, and subword-free languages are defined similarly, where "subword…
Quotient Complexity of Closed Languages
J. Brzozowski, G. Jirásková, C. Zou
A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in the same way, where by…
Quotient complexity of ideal languages
J. Brzozowski, G. Jirásková, B. Li
We study the state complexity of regular operations in the class of ideal languages. A language L over an alphabet Sigma is a right (left) ideal if it satisfies L = L Sigma* (L = S…
Nondeterministic State Complexity of Positional Addition
Galina Jirásková, Alexander Okhotin
Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved…