BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Szabolcs Ivan contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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.
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$.
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.
We give a Kleene-type operational characterization of Muller context-free languages (MCFLs) of well-ordered and scattered words.