A reconstruction algorithm for L-convex polyominoes

AbstractWe give an algorithm that uniquely reconstruct an L-convex polyomino from the size of some special paths, called bordered L-paths.

Comparison of central venous catheterization with and without ultrasound guide

Purpose: To compare the effectiveness, safety and time needed to perform central venous catheterization (CVC) in the presence or absence of an ultrasound (US) guide. Methods: Between January 1999 and February 2002 we performed CVCs in 196 patients: 105 patients received US guided CVC (group I) and 91 patients had CVC without US guide (group II). Results: The average time to perform CVC was shorter with US guide (4 vs 7min). The utilization of the US guide was also associated with improved success (98.09% vs 91.2%, p < 0.025) and lack of major complications (0% vs 9.8%, p < 0.001). Conclusions: US-guided CVC affords an easier, safer and more rapid cannulation of a central vein. It is especia…

A graph theoretic approach to automata minimality

AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.

Extremal minimality conditions on automata

AbstractIn this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automato…

Some Remarks on Automata Minimality

It is well known that the minimization problem of deterministic finite automata (DFAs) is related to the indistinguishability notion of states (cf. [HMU00]). Indeed, a well known technique to minimize a DFA, essentially, consists in finding pairs of states that are equivalent (or indistinguishable), namely pairs of states (p,q) such that it is impossible to assert the difference between p and q only by starting in each of the two states and asking whether or not a given input string leads to a final state. Since, in the testing states equivalence, the notion of initial state is irrelevant, some of the main techniques for the minimization of automata, such as Moore’s algorithm [Moo56] and Ho…

Recognizable picture languages and polyominoes

We consider the problem of recognizability of some classes of polyominoes in the theory of picture languages. In particular we focus our attention oil the problem posed by Matz of finding a non-recognizable picture language for which his technique for proving the non-recognizability of picture languages fails. We face the problem by studying the family of L-convex polyominoes and some closed families that are similar to the recognizable family of all polyominoes but result to be non-recognizable. Furthermore we prove that the family of L-convex polyominoes satisfies the necessary condition given by Matz for the recognizability and we conjecture that the family of L-convex polyominoes is non…

Recognizable Picture Languages and Polyominoes

Automata with Extremal Minimality Conditions

It is well known that the minimality of a deterministic finite automaton (DFA) depends on the set of final states. In this paper we study the minimality of a strongly connected DFA by varying the set of final states. We consider, in particular, some extremal cases. A strongly connected DFA is called uniformly minimal if it is minimal, for any choice of the set of final states. It is called never-minimal if it is not minimal, for any choice of the set of final states. We show that there exists an infinite family of uniformly minimal automata and that there exists an infinite family of never-minimal automata. Some properties of these automata are investigated and, in particular, we consider t…

Ultrasound (US) guided central venous catheterization of internal jugular vein on over 65-year-old patients versus blind technique.

Background and Objectives Performing a central venous catheterization (CVC) on older patients for long-term central intravenous therapy could be a very important procedure. It could be associated with a high incidence of related complications, especially on over 65-year-old, high risk, selected patients. Methods The authors analyzed the results of 72 central venous CVC of internal jugular vein performed on over 65-year-old patients with ultrasound (US) guide from January 1998 to April 2003. Results The average performing time was 4 min, with 98.7% of success, 0% of major complications, and 4.1% of minor complications (one mild vagal hypotension and two catheter dislocation). Conclusions The…