1,721,002 research outputs found
Decremental 2- and 3-connectivity on planar graphs
No full textWe study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components
of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained
in a total of O(n logn) time under any sequence of at most O(n) deletions. This gives O(logn) amortized
time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O (n log 2 n)
time. This gives O(log 2 n) amortized time per deletion. The space required by all our data structures is O(n).
All our time bounds improve previous bounds
Exploring inside Tiling Recognizable Picture Languages to Find Deterministic subclasses
No full textTiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless family REC is not closed under complementation and this implies that it is intrinsically non-deterministic. We consider different notions of unambiguity and determinism and the corresponding REC subclasses: they define a hierarchy inside REC. We show that some definitions of unambiguity are equivalent to particular notions of determinism and therefore the corresponding classes have linear parsing algorithms and are closed under complementation
Formal Languages and Automata: Models, Methods and Application. In Honour of the 70th Birthday of Antonio Restivo Preface
No full textA Common Framework to Recognize Two-dimensional Languages
No full textWe introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages
Isometric words and edit distance: main notions and new variations
No full textIsometric words combine the notion of edit distance together with properties of words not appearing as factors in other words. An edit distance is a metric between words that quantifies how two words differ by counting the number of edit operations needed to transform one word into the other one. A word f is said isometric with respect to an edit distance if, for any pair of f-free words u and v, there exists a transformation of minimal length from u into v via the related edit operations such that all the intermediate words are also f-free. The adjective “isometric” comes from the fact that, if the Hamming distance is considered (i.e., only replacement operations are used), then isometric words are connected with the definitions of isometric subgraphs of hypercubes. We discuss known results and some interesting generalizations and open problems
New operations and regular expressions for two-dimensional languages over one-letter alphabet
No full textWe consider the problem of defining regular expressions to characterize the class of recognizable
picture languages in the case of a one-letter alphabet.We define a diagonal concatenation and its star
and consider two different families, L(D) and L(CRD), of languages denoted by regular expressions
involving such operations plus classical operations. L(D) is characterized both in terms of rational
relations and in terms of two-dimensional automata moving only right and down. L(CRD) is included
inRECand contains languages defined by three-way automata while languages in L(CRD) necessarily
satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing
the necessity of conceptually different definitions for iteration
Computing languages by (bounded) local sets
No full textWe introduce the definition of local structures as description of computations to recognize strings and characterize families of Chomsky's hierarchy in terms of projection of frontiers of local sets of structures. Then we consider particular grid structures we call bounded-grids and study the corresponding family of string languages by proving some closure properties and giving several examples
A Common framework to recognize two-dimensional languages
No full textWe introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages
Sets of Pictures Avoiding Overlaps
No full textA string set avoids overlaps if it has the property that the prefix of each string in the set does not coincide with the suffix of any string in the set. The problem of avoiding overlaps in strings is extensively investigated since it plays an important role in the context of string matching and coding. The notion of overlap can be extended naturally to two dimensions; two pictures p and q have an overlap if one can put one corner of p on some position in q in such a way that all symbols in the common positions coincide. A picture with no self-overlaps is called unbordered and it is a generalization in two dimensions of an unbordered (or bifix-free) string.We first investigate the problem of generating all unbordered pictures of fixed size. Then, we study particular sets of unbordered pictures that are non-overlapping each others. We show that the frame of the pictures has a special role in defining these sets. In particular, we prove that there exist kinds of synchronization frames that can be put around the pictures of any set to make it non-overlapping. Finally, we present a construction of non-expandable non-overlapping sets of pictures which starts from some property of frame-completeness.
The research that led to the present paper was partially supported by a grant of the group GNCS of INdAM
- …
