Source author record

Szabolcs Ivan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Data Structures and Algorithms

Catalog footprint

Research overview

6works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Complexity of Atoms, Combinatorially

Atoms of a (regular) language $L$ were introduced by Brzozowski and Tamm in 2011 as intersections of complemented and uncomplemented quotients of $L$ . They derived tight upper bounds on the complexity of atoms in 2013. In 2014, Brzozowski and Davies characterized the regular languages meeting these bounds. To achieve these results, they used the so-called "atomaton" of a language, introduced by Brzozowski and Tamm in 2011. In this note we give an alternative proof of their characterization, via a purely combinatorial approach.

preprint2014arXiv

On nonpermutational transformation semigroups with an application to syntactic complexity

We give an upper bound of $n((n-1)!-(n-3)!)$ for the possible largest size of a subsemigroup of the full transformational semigroup over $n$ elements consisting only of nonpermutational transformations. As an application we gain the same upper bound for the syntactic complexity of (generalized) definite languages as well.

preprint2014arXiv

On state complexity of unions of binary factor-free languages

It has been conjectured in 2011 by Brzozowski et al. that if $K$ and $L$ are factor-free regular languages over a binary alphabet having state complexity $m$ and $n$ , resp, then the state complexity of $K\cup L$ is at most $mn-(m+n)+3-\min\{m,n\}$ . We disprove this conjecture by giving a lower bound of $mn-(m+n)-2-\lfloor\frac{\min\{m,n\}-2}{2}\rfloor$ , which exceeds the conjectured bound whenever $\min\{m,n\}\geq 10$ .

preprint2013arXiv

On the structure and syntactic complexity of generalized definite languages

We give a forbidden pattern characterization for the class of generalized definite languages, show that the corresponding problem is NL-complete and can be solved in quadratic time. We also show that their syntactic complexity coincides with that of the definite languages and give an upper bound of n! for this measure.

preprint2013arXiv

Operational characterization of scattered MCFLs -- Technical Report

We give a Kleene-type operational characterization of Muller context-free languages (MCFLs) of well-ordered and scattered words.

preprint2011arXiv

Context-free ordinals

We consider context-free languages equipped with the lexicographic ordering. We show that when the lexicographic ordering of a context-free language is scattered, then its Hausdorff rank is less than $ω^ω$ . As a corollary of this result we obtain that an ordinal is the order type of a well-ordered context-free language iff it is less than $ω^{ω^ω}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.