BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Galina Jirásková

Galina Jirásková contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata Theory

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

5 published item(s)

preprint2014arXiv

On Upper and Lower Bounds on the Length of Alternating Towers

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 other language, and each string can be embedded into the next string in the sequence. It is known that if there are towers of any length, then there also exists an infinite tower. We investigate upper and lower bounds on the length of finite towers between two regular languages with respect to the size of the automata representing the languages in the case there is no infinite tower. This problem is relevant to the separation problem of regular languages by piecewise testable languages.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the State Complexity of the Reverse of R- and J-trivial Regular Languages

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 regular languages and (n-1)-ary for J-trivial regular languages. In this paper, we prove that the bound can be met neither by a binary R-trivial regular language nor by a J-trivial regular language over an (n-2)-element alphabet. We provide a characterization of tight bounds for R-trivial regular languages depending on the state complexity of the language and the size of its alphabet. We show the tight bound for J-trivial regular languages over an (n-2)-element alphabet and a few tight bounds for binary J-trivial regular languages. The case of J-trivial regular languages over an (n-k)-element alphabet, for 2 <= k <= n-3, is open.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages

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 &#34;subword&#34; means &#34;subsequence&#34;. A language is bifix-free if it is both prefix- and suffix-free. We study the quotient complexity, more commonly known as state complexity, of operations in the classes of bifix-, factor-, and subword-free regular languages. We find tight upper bounds on the quotient complexity of intersection, union, difference, symmetric difference, concatenation, star, and reversal in these three classes of languages.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Complexity in Prefix-Free Regular Languages

We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over smaller alphabets, usually as small as possible. We next provide the tight bounds on state complexity of symmetric difference, and deterministic and nondeterministic state complexity of difference and cyclic shift of prefix-free languages.

0 citations0 reviewsNo code linkedOpen access