1,721,061 research outputs found
CISTECTOMIA RADICALE VIDEOLAPAROSCOPICA VS CISTECTOMIA OPEN: LA NOSTRA ESPERIENZA Solinas,T., G.I. Russo, I. Pecori, G. Morgia, Madonia, M.
No full text
A computational model for tiling recognizable two-dimensional languages
No full textTiling systems are a well accepted model to define recognizable two-dimensional
languages but they are not an effective device for recognition unless a scanning strategy
for the pictures is fixed. We define a tiling automaton as a tiling system equipped with
a scanning strategy and a suitable data structure. The class of languages accepted by
tiling automata coincides with the REC family. In this framework it is possible to define
determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are
compared with the other known (deterministic) automata models for two-dimensional
languages
From determinism to non-determinism in recognizable two-dimensional languages
No full textTiling systems that recognize two-dimensional languages are intrinsically non-deterministic models. We introduce the notion of deterministic tiling system that generalizes deterministic automata for strings. The corresponding family of languages matches all the requirements of a robust deterministic class. Furthermore we show that, differently from the one-dimensional case, there exist many classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties. © Springer-Verlag Berlin Heidelberg 2007
Tiling automaton: a Computational Model for Recognizable Two-dimensional Languages
No full textTwo-dimensional languages can be recognized by tiling systems. A tiling system becomes an effective device for recognition when a scanning strategy on pictures is fixed. We define a Tiling Automaton as a tiling system together with a scanning strategy and a suitable data structure. In this framework it is possible to define determinism, non-determinism and unambiguity. The class of languages accepted by tiling automata coincides with REC family. Tiling automata are able to simulate on-line tessellation automata. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for recognition of two-dimensional languages. © Springer-Verlag Berlin Heidelberg 2007
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
On k-ary n-cubes and isometric words
No full textThe k-ary n-cubes are a generalization of the hypercubes to alphabets of cardinality k, with k>=2. More precisely, a k-ary n-cube is a graph with k^n vertices associated to the k-ary words of length n. Given a k-ary word f, the k-ary n-cube avoiding f is the subgraph obtained deleting those vertices which contain f as a factor. When such a subgraph is isometric to the cube, for any n>=1, the word f is said isometric. A binary word f is isometric if and only if it is Ham-isometric, i.e., for any pair of f-free binary words u and v, u can be transformed in v by complementing the bits on which they differ and generating only f-free words. The case of a k-ary alphabet, with k>=2, is here investigated. From k>=4, the isometricity in terms of cubes is no longer captured by the Ham-isometricity, but by the Lee-isometricity. Then, Ham-isometric and Lee-isometric k-ary words are characterized in terms of their overlaps with errors. The minimal length of two words which witness the non-isometricity of a word f is called its index. The index of f is bounded in terms of its length and the bounds are shown tight by examples
Deterministic and Unambiguous Two-dimensional Languages over One-letter Alphabet
No full textThe paper focuses on deterministic and unambiguous recognizable two-dimensional
languages with particular attention to the case of a one-letter alphabet. The family DREC(1)
of deterministic languages over a one-letter alphabet is characterized as both L(DOTA)(1),
the class of languages accepted by deterministic on-line tessellation acceptors, and
L(2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We
show that there are inherently ambiguous languages and unambiguously recognizable
languages that cannot be deterministically recognized even in the case of a one-letter
alphabet. In particular we show that on-line tessellation acceptors are more powerful than
their deterministic counterpart, even in the case of a one-letter alphabet. Finally we show
that DREC(1) is complex enough not to be characterized in terms of classical operations
- …
