Search results for "monadi"

The Monadic Quantifier Alternation Hierarchy over Grids and Graphs

2002

AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrar…

The monadic quantifier alternation hierarchy over grids and pictures

1998

The subject of this paper is the expressive power of monadic second-order logic over two-dimensional grids. We give a new, self-contained game-theoretical proof of the nonexpressibility results of Matz and Thomas. As we show, this implies the strictness of the monadic second-order quantifier alternation hierarchy over grids.

Local Normal Forms for First-Order Logic with Applications to Games and Automata

1999

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…

Molecular phylogeny of parabasalids with emphasis on the order Cristamonadida and its complex morphological evolution

2009

1055-7903 doi: DOI: 10.1016/j.ympev.2009.03.011; Parabasalia represents a complex assemblage of species, which recently received extensive reorganization. The newly created order Cristamonadida unites complex hypermastigids belonging to the Lophomonadida like the joeniids, the multinucleate polymonad Calonymphidae, and well-developed trichomonads in the Devescovinidae. All these protists exclusively occur in the guts of termites and related insects. In this study, small subunit rRNA and glyceraldehyde-3-phosphate dehydrogenase genes were identified without cultivation from 14 species in Cristamonadida including previously unstudied genera such as Joenina, Joenia, Joenoides, Macrotrichomonas…

Ultrastructure and Organization of the Cytoskeleton in Oxymonas, an Intestinal Flagellate of Termites

1997

ABSTRACT. Oxymonas has the characteristic structures and organization of other oxymonads including two separated pairs of basal bodies/flagella, a preaxostylar lamina, a paracrystalline axostyle, and an absence of mitochondria and Golgi. Like other Oxymonadinae genera it possesses a long proboscis, the rostellum which is terminated by the holdfast. Like the genera Pyrsonympha and Streblomastix, Oxymonas possesses a holdfast which permits it to attach to the cuticle of the termite hind-gut. This holdfast is subdivided into rhizoids and is filled with microfilaments. The rostellum is variable in length and contains two distinct microtubular bundles. One bundle is composed of convoluted microt…

Ethidium bromide: a fast fluorescent staining procedure for the detection of symbiotic partnership of flagellates and prokaryotes

1999

The hindgut of 'lower' termites harbors a dense population of flagellates and bacteria. The flagellates possess ecto- and endosymbiotic prokaryotes. Most of them are hardly visible in the phase contrast microscope. Staining with the DNA-intercalating agent ethidium bromide visualizes the nuclei of the flagellates as well as the ecto- and endosymbiotic bacteria as red objects. Furthermore, it is possible to distinguish between endosymbiotic methanogens and other bacteria. Following UV excitation, the blue-green autofluorescence of the methanogenic bacteria eclipses the red fluorescence light of the intercalated ethidium bromide. The dye facilitates the observation of symbiotic bacteria and h…

Tra monadi e tessuti preesistenti

2017

Il rapporto che un progettista ha con la propria città natale è una delle prime fonti da indagare per comprendere se e in che modo alcune peculiarità dello spazio urbano, vissuto quotidianamente, trovano eco o si rispecchiano integralmente nel lavoro dello stesso architetto. Seguendo tale direzione di approfondimento, si vogliono inquadrare i progetti di Angelo Torricelli per Milano, proponendo un iniziale confronto fra due di erenti affermazioni. La prima di Chiara Baglione, la seconda dello stesso Torricelli. Dalle due frasi sembra scaturire, di fatto, una coincidenza fra il modo di essere di una città, Milano per l’appunto, e le qualità intrinseche delle architetture di Torricelli, in gr…

Monadic second-order logic over pictures and recognizability by tiling systems

1994

We show that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system if and only if it is definable in existential monadic second-order logic. As a consequence, finite tiling systems constitute a notion of recognizability over two-dimensional inputs which at the same time generalizes finite-state recognizability over strings and matches a natural logic. The proof is based on the Ehrenfeucht-FraIsse technique for first-order logic and an implementation of “threshold counting” within tiling systems.

Monadic Second-Order Logic over Rectangular Pictures and Recognizability by Tiling Systems

1996

Abstract It is shown that a set of pictures (rectangular arrays of symbols) is recognized by a finite tiling system iff it is definable in existential monadic second-order logic. As a consequence, finite tiling systems constitute a notion of recognizability over two-dimensional inputs which at the same time generalizes finite-state recognizability over strings and also matches a natural logic. The proof is based on the Ehrenfeucht–Fraisse technique for first-order logic and an implementation of “threshold counting” within tiling systems.

Bacterial Ectosymbionts which Confer Motility: Mixotricha paradoxa from the Intestine of the Australian Termite Mastotermes darwiniensis

2005