Source author record

Alessandra Cherubini

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 math.CO math.GR

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Composing short 3-compressing words on a 2 letter alphabet

A finite deterministic (semi)automaton $\mathcal{A} =(Q,Σ,δ)$ is $k$ -compressible if there is some word $w\in Σ^+$ such that the image of its state set $Q$ under the natural action of $w$ is reduced by at least $k$ states. Such word, if it exists, is called a $k$ -compressing word for $\mathcal{A}$ . A word is $k$ -collapsing if it is $k$ -compressing for each $k$ -compressible automaton. We compute a set $W$ of short words such that each $3$ -compressible automata on a two letter alphabet is $3$ -compressed at least by a word in $W$ . Then we construct a shortest common superstring of the words in $W$ and, with a further refinement, we obtain a $3$ -collapsing word of length $53$ . Moreover, as previously announced, we show that the shortest $3$ -synchronizing word is not $3$ -collapsing, illustrating the new bounds $34\leq c(2,3)\leq 53$ for the length $c(2,3)$ of the shortest $3$ -collapsing word on a two letter alphabet.

preprint2013arXiv

Maximal subgroups of amalgams of finite inverse semigroups

We use the description of the Schutzenberger automata for amalgams of finite inverse semigroups given by Cherubini, Meakin, Piochi to obtain structural results for such amalgams. Schutzenberger automata, in the case of amalgams of finite inverse semigroups, are automata with special structure possessing finite subgraphs, that contain all essential information related to the whole automaton. Using this crucial fact, and the Bass-Serre theory, we show that the maximal subgroups of an amalgamated free-product are either isomorphic to certain subgroups of the original semigroups or can be described as fundamental groups of particular finite graphs of groups build from the maximal subgroups of the original semigroups.

preprint2011arXiv

A unifying approach to picture grammars

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using a tiling based approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling,named regional, and define the corresponding regional tile grammars. They include both Siromoney's (or Matz's) Kolam grammars and their generalization by Prusa, as well as Drewes's grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).

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.