Browsing Mathematics (Faculty of) by Author "Szykuła, Marek"
Now showing items 14 of 4

Complexity of SuffixFree Regular Languages
Brzozowski, Janusz; Szykuła, Marek (Elsevier, 20171101)We study various complexity properties of suffixfree regular languages. A sequence (Lk,Lk+1,…) of regular languages in some class, where n is the quotient complexity of Ln, is most complex if its languages Ln meet the ... 
Large Aperiodic Semigroups
Brzozowski, Janusz; Szykuła, Marek (World Scientific Publishing, 20151101)We search for the largest syntactic semigroups of starfree languages having n left quotients; equivalently, we look for the largest transition semigroups of aperiodic finite automata with n states. We first introduce ... 
Syntactic Complexity of Regular Ideals
Brzozowski, Janusz; Szykuła, Marek; Ye, Yuli (Springer, 20170804)The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic ... 
Syntactic Complexity of SuffixFree Languages
Brzozowski, Janusz; Szykuła, Marek (Elsevier, 20170905)We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffixfree language with n left quotients (that is, with state complexity n) is at most (n−1)n−2+n−2 ...