Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Estudo Estratigráfico e Paleontológico do Jurássico do Algarve Ocidental

Algarve Province, Southern Portugal, corresponds in part to a meso-cenozoic basin running along the coast from Cabo S. Vicente to beyond Spanish border. Structurally it is a big monocline plunging southwards much deformed mainly by two East-West longitudinal flexures. Lithostratigraphical and chronostratigraphical studies dealt specially with Jurassic formations. This and the geological mapping of the post-Hercynian sedimentary formations allow us to define the following units: Triassic-Lower Liassic Arenitos de Silves (Silves sandstones sensu P. Choffat, pro parte) - At their base the Silves sandstones (0-150m) are represented mainly by cross-bedded red sandstones. This unit is Upper Triassic (Keuper) in age, on the evidence of some Brachiopoda. Complexo margo-carbonatado de Silves (Silves marl-limestone complex=Silves sandstones sensu P. Choffat, pro parte) (80-200m) overlies the preceding, it may be reported to the Upper Triassic-Hettangian. It consists of a thick pelite-marl-dolomite-limestone series with many intercalations of greenstones. Since no fossils were found it is not possible to conclude whether it is still Hettangian or if it does correspond, in the whole or in part, already to the Sinemurian. Liassic Dolomitos e calcários dolomíticos de Espiche (Espiche dolomite-rocks and dolomitic-limestones) - The usually massive and finely crystalline or saccharoidal dolomites and dolomitic-limestones are the toughest strata of the Algarve margin giving rise to several hills. Its thickness attains in certain points 60 metres at least. Based on geometry and on lithological similarities with the carbonated complex of the northern basin of Tagus river (Peniche, São Pedro de Muel, Quiaios), this formation can be accepted as Sinemurian in age. As it happens with the carbonated complex, here also the first dolomite beds are non-isochronal throughout the region; upper time-limit of the dolomitic facies is either Lower Carixian, Lower Toarcian or even Lower Dogger. The dolomitization is secondary but not much later than sedimentation. However, between Cabo S. Vicente-Vila do Bispo there is evidence of an even later secondary dolomitization related to the regional fault complex. Calcário dolomítico com nódulos de silex da praia de Belixe (Belixe beach dolomitic-limestone with silex nodules) (50-55m) - Ascribed to Lower or Middle Carixian on the basis of Platypleuroceras sp., Metaderoceras sp. nov. and M. gr. Venarense. Calcário cristalino compacto com Protogrammoceras, Fuciniceras e ? Argutarpites de Belixe (Belixe compact crystalline limestone with Protogrammoceras, Fuciniceras and ? Argutarpites) (30m) - Ascribed to Lower Domerian. Middle and Upper Domerian are indicated but by a single specimen of ? Argutarpites. Calcários margosos e margas com Dactylioceras semicelatum e Harpoceratídeos de Armação Nova (Armação Nova marly limestones and marls with D. semicelatum and Harpoceratidae) (25m) -Ascribed to Lower Toarcian. Middle and Upper Toarcian formations are not known in the Algarve. Dogger Calcários oolíticos, c. corálicos, c. pisolíticos, c. calciclásticos, c. dolomíticos e dolomitos de Almadena (Almadena oolitic-limestones, coral-reef-limestones, pisolite-limestones, limeclastic-limestones, dolomitic-limestones and dolomite-rocks) (more than 50 metres), with lagoonal facies. Ascribed to Aalenian-Bathonian-? Callovian. Margas acinzentadas e calcários detríticos com Zoophycos da praia de Mareta (Mareta beach greyish marls and detritical limestones with Zoophycos) (40m) - Pelagic transreef facies with Upper Bajocian and Bathonian ammonites. Calcários margosos e margas da praia de Mareta (Mareta beach pelagic marly-limestones and marls) (110m) - Ascribed to the Callovian on its ammonites. Malm Near Cabo S. Vicente and Sagres the first Upper Jurassic level consists of a yellowish-brown nodular, compact, locally phosphated and ferruginous, sometimes conglomeratic, marly limestone (0,35-1,50m) containing a rich macrofauna, which includes: 1) Callovian forms unknown at Lower Oxfordian; 2) Upper Callovian forms that still survived in Lower and Middle Oxfordian; 3) Lower Oxfordian forms (Mariae and Cordatum Zones); 4) Lower and Middle Oxfordian forms (Mariae to Plicatilis Zone); 5) Middle Oxfordian forms (plicatilis Zone), and some ones appearing in Middle Oxfordian. This condensed deposit is therefore dated from Middle Oxfordian (Plicatilis Zone). The other Upper Jurassic lithostratigraphical units were also mapped but their detailed study is not presented in this work. Correlations between lithostratigraphical and chronostratigraphical scales from P. Choffat, J. Pratsch, C. Palain and from the author are stated. Further correlations are attempted between zonc scales of Carixian-Lower Toarcian and Upper Bajocian-Middle Oxfordian of France, Spain (Asturias, Iberian and Betic Chains), Argel (Orania) and Portugal (northern Tagus basin and Algarve). The study of pyritous fossil assemblages common in Upper Bathonian-Lower Callovian marly levels of the praia da Mareta seems to suggest that these sediments were deposited in a bay or in an almost closed coastal re-entrance virtually without deep water circulation. Although such conditions may occur at any depth one may suppose that these ones actually correspond to an infralittoral neritic environment. The thaphocoenosis collected there are almost entirely composed of nektonic (ammonites, Belemnites) and planktonic (Bositra) faunas. The sedentary (crinoids, brachiopods) or free (sea-urchins, gastropods) epibenthonic forms are very scarce; endobenthonic forms are not known. The palaeontological study of all Nautiloids and Ammonoids of the Liassic and Dogger is presented (except Kosmoceratidae and Perisphinctaceae). Among the thirty one taxa dealt with, one is new (Metaderoceras sp. nov.) and the great majority of the others has been identified for the first time in Algarve. Some others have never been reported before in Portuguese formations. The evolution, during Jurassic times, of the sedimentary basins of the Portuguese plate margin is described. The absence of Cephalopods in the very extensive marly and dolomitic limestones, partly marine, suggests that, during Lower Liassic, palaeogeography underwent no great changes. Dolomitic-limestone with silex nodules from Cabo S. Vicente contain the first ammonites recorded at the base of the Middle Liassic. This facies, although very common in Tethys, is unknown north of the Tagus. The faunal assemblage has a mediterranean to submediterranean character. Comparisons between faunal assemblage" from Algarve with the ones known north of the Tagus show that communications between Boreal Europe and Tethys, virtually non-existent during Lower and Middle Carixian, became very easy during Lower Domerian. In earlier Pliensbachian times two distinct seas were adjacent to the Iberian plate. One, an epicontinental sea with a tethyan fauna, extended southwards from the Meseta margin. Another, was a boreal sea; during its transgressive episodes boreal faunas attained into the basin north of the Tagus. During Middle Carixian and Lower Domerian, owing to simultaneous transgressions, these two seas joined together allowing faunal exchanges along the epicontinental areas which limited the emerging hercynian chains belts. During Liassic, the Algarve belonged undoubtedly to the tethyan submediterranean province. The area north of the Tagus, on the contrary, was a complex realm where subboreal and tethyan affinities alternatively prevailed. In the Algarve the first Middle Jurassic deposits do frequently show lateral thickness reductions as well as unconformities contemporaneous with other generalized disturbances on the sedimentation processes in other parts of Europe. By this time, near Sagres, a barrier reef developed separating lagoonal or ante-reef facies from the transreef pelagic zone. The presence of tethyan fauna, the abundance of Phylloceratidae and the absence of boreal forms allow us to consider the Algarve basin as a submediterranean province. The presence of Callovian pelagic fossiliferous formations in the Loulé area shows that during Middle Jurassic the marl-limestone transreef sedimentation was not confined to the western Algarve. They would extend eastwards where they only can be seen in the core of some anticlines. This is due to the progressive sinking of the meso-cenozoic formations as we proceed towards the South of the Sagres-Algoz-Querença flexure. In the whole of the Peninsule, and as for the Middle Callovian, an important regression can be clearly recognized on the evidence of an erosion surface which strikes obliquely the Middle and Upper Callovian strata. The geographic boundaries of the different faunal provinces are not changed by the presence of many Kosmoceratidae in the phosphate nodules since they are but a minority in comparison with the tethyan forms. An abstract model can be constructed showing that in Western Europe the Kosmoceratidae may have migrated South and westwards through a channel of the sea that linked Paris basin to Poitou and Aquitaine. By migrating between the Iberian meseta and the Armorican massif this fauna reached northern Tagus basin at the beginning of Upper Callovian (Athleta Zone); this south and southwest bound migration would have proceeded, allowing such forms to reach Algarve basin only in latest Callovian times (Lamberti Zone). This migration means that during Middle Jurassic a widely spread North Atlantic sea would exist, flooding the western part of Portugal up to the Poitou.

Evolução tectónica mesozóica da Bacia Lusitaniana

The evolution of the Lusitanian Basin, localized on the western Iberian margin, is closely associated with the first opening phases of the North Atlantic. It persisted from the Late Triassic to the Early Cretaceous, more precisely until the end of the Early Aptian, and its evolution was conditioned by inherited structures from the variscan basement. The part played by the faults that establish its boundaries, as regards the geometric and kinematic evolution and the organization of the sedimentary bodies, is discussed here, as well as with respect to important faults transversal to the Basin. A basin evolution model is proposed consisting of four rifting episodes which show: i) periods of symmetrical (horst and graben organization) and asymmetrical (half graben organization) geometric evolution; ii) diachronous fracturing; iii) rotation of the main extensional direction; iv) rooting in the variscan basement of the main faults of the basin (predominantly thick skinned style). The analysis and regional comparison, particularly with the Algarve Basin, of the time intervals represented by important basin scale hiatuses near to the renovation of the rifting episodes, have led to assume the occurrence of early tectonic inversions (Callovian–Oxfordian and Tithonian–Berriasian). The latter, however, had a subsequent evolution distinct from the first: there is no subsidence renovation, which is discussed here, and it is related to a magmatic event. Although the Lusitanian Basin is located on a rift margin which is considered non-volcanic, the three magmatic cycles as defined by many authors, particularly the second (approx. 130 to 110 My ?), performed a fundamental part in the mobilization of the Hettangian evaporites, resulting in the main diapiric events of the Lusitanian Basin. The manner and time in which the basin definitely ends its evolution (Early Aptian) is discussed here. Comparisons are established with other west Iberian margin basins and with Newfoundland basins. A model of oceanization of this area of the North Atlantic is also presented, consisting of two events separated by approximately 10 My, and of distinct areas separated by the Nazaré fault. The elaboration of this synthesis was based on: - information contained in previously published papers (1990 – 2000); - field-work carried out over the last years, the results of which have not yet been published; - information gathered from the reinterpretation of geological mapping and geophysical (seismic and well logs) elements, and from generic literature concerning the Mesozoic of the west iberian margin.

Le Crétacé inférieur de la marge atlantique portugaise: biostratigraphie, organization séquentielle, evolution paléogéographique

This paper gives a short description of main stratigraphic unities from the early Cretaceous in Estremadura and Algarve, with their lithological, sedimentological and paleontological characteristics. The distribution of facies enable to propose a paleogeographic frame including eroded high areas and sedimentary low areas roughly parallel to the present coast. The early Cretaceous from Estremadura is splited up into three megasequences each one with regressive then transgressive tendencies: this fact must be connected with the leading action of distensive, slow or sudden, movements. Beyond the hercynian fault of Messejana, Algarve presents a different sedimentary evolution during the early Cretaceous.

A shared-disk parallel cluster file system

Dissertação apresentada para obtenção do Grau de Doutor em Informática Pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Geodynamics of the eastern sector of the Arrábida chain (W Portugal)

N.º4, p.263-267

Caracterização de estruturas tectónicas activas da região sul de Portugal com recurso a ferramentas SIG: o caso da falha de São Marcos - Quarteira

Dissertação apresentada como requisito parcial para obtenção do grau de Mestre em Ciência e Sistemas de Informação Geográfica

Estratigrafia e interpretação paleogeográfica do Cenozóico continental do norte de Portugal

Palaeogeographic and tectono-sedimentary interpretation of northern Portugal, in which previous studies (geomorphology, lithostratigraphy, mineralogy, sedimentology, palaeontology, etc.) were considered, is here proposed. Cenozoic shows different features according to its morphotectonic setting in the eestern region (Trás-os-Montes) or near to the Atlantic coast (western region, Minho and Douro Litoral areas). Although in the eastern region the sedimentary record is considered late Neogene, in some places Paleogene (?) was identified. This oldest record, represented by alluvial deposits, was preserved from complete erosion because of its position inside Bragança-Vilariça-Manteigas fault zone grabens. Later sedimentary episodes (upper Tortonian-Zanclean ?), represented by two allostratigraphical units, were interpreted as proximal fluvial braided systems of an endorheic hydrographic network, draining to the Spanish Duero Basin (eastwards); nowadays, they still remained in tectonic depressions and incised-valleys. Later on, eastern sedimentation becomes scarcer because Atlantic fluvial systems (e.g. the pre-Douro), successively, captured previous endorheic drainages. The proximal reaches of the allostratigraphic unit considered Placencian is recorded in Mirandela (western Trás-os-Montes) but the following fluvial episode (Gelasian-early Pleistocene ?) was already documented in east Trás-os-Montes, preserved in high platforms and in tectonic depressions. Placencian and Quaternary sedimentary records in the western coastal zone, mainly represented by terraces, are located in the Minho, Lima, Alverães, Cávado and Ave large fluvial valleys and in the Oporto littoral platform. In conclusion, northern Portugal Tertiary sedimentary episodes were mainly controlled by tectonics, but later on (Placencian-Quaternary) also by eustasy.

Evolução cenozóica da área de Longroiva-Vilariça (NE Portugal)

In the Longroiva-Vilariça area, the identification of Cenozoic lithostratigraphic units, the sedimentology and the characterization of its geometric relations with tectonic structures allowed the interpretation of the palaeogeographic main stages: 1) the greenwhitish Vilariça Arkoses (Middle Eocene to Oligocene ?) represent proximal sediments of a very low gradient drainage towards the eastern Spanish Tertiary Duero Basin; 2)Quintãs Formation (late Miocene ?) are brown-reddish coloured piedmont alluvial deposits, correlative of important vertical displacement (western tectonic block relative uplift) along the NNE-SSW indent-linked strike-slip Bragança-Vilariça-Longroiva fault zone, interpreted as a reactivated deep hercynian fracture, with left-lateral movement; 3) the red Sampaio Formation (Gelasian-early Pleistocene ?)was interpreted as downhill conglomeratic deposits related with important overtrusting along this fault zone (the definition of the present-day narrow graben configuration) and correlative of the atlantic hydrographic incision stage beginning; 4) conglomeratic terraces (middle and late Pleistocene ?); 5) alluvial plains and colluvial deposits (Holocene).

Contribuição para a análise tectono-sedimentar do Fosso de Aljezur (SW de Portugal)

The Aljezur "graben" is a crucial piece in understanding the Caenozoic evolution of the SW atlantic portuguese edge. Detailed study of the sedimentary filling and bordering accidents allows the identification of several evolution steps since the Miocene. The graben is bordered by accidents that dislocate geomorphologic surfaces (Littoral Platform to the W, Interior Platform to the E), and also Neogene sedimentary units. The sedimentary filling is composed by conglomerates and sands grading into clays and bioclastic limestones (Burdigalian to Serravalian), upon which lie unconformably fine reddish sands, sometimes with abundant micas. Genetic and geometric relationships between these sands, those in higher surfaces outside the "graben" and the main bordering faults, are discussed. As a conclusion, the reconstruction of the tectono-sedimentary evolution is attempted, integrating it in a "pull-apart" context associated with the Messejana-fault system and it's reactivation by the differently orientated alpine compressions.

Estratigrafia sismica do cenozóico na plataforma continental algarvia: interpretação do controle tectónico da sedimentação

The interpretation of 64 seismic reflection profiles in the Algarve continental platform (36º 20'-37º 00' paralels and 7º 20'-8º 40' meridians) calibrated with five petroleum exploration wells, with the identification of the geometric relations between six Cenozoic seismic units (B to G) and tectonic structures, allowed the construction of sucessive time-isopach maps (twt/s) and detailed interpretation of the geologic evolution. Two major tectonic structures were identified: a) the Portimão-Monchique fracture zone (striking N-S); b) an off-shore NW-SE fault zone, probably the S. Marcos-Quarteira fault. This accident separates two tectonic domains: the western domain (with N-S and E-W predominant structures and, secondarily, NW-SE and NE-SW) and the eastern domain (dominated by WSW-ENE, NW-SE, NE-SW, NNE-SSW and NNW-SSE structures). A persistent halokinetic activity had two major moments: a) sin-C unit; b) sin- and post-E unit. An increasing flexuration of the margin was identified, with spacial and temporal variation of the subsidence. The tectonic regime is considered as generally compressive, but the interpretation of the successíve stress-fields is rendered dificult by the existence of tectonic sub-domains and evaporitic structures.

Diagnosis of an EPS module

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Electrotécnica e Computadores

Tectónica da região de Sintra

Photo-interpretation of aerial stereopairs of the Sintra region on the approx. 1/32 000 scale together with field work allowed the production of the present Tectonic Map of the Sintra region. It is now possible to separate structures which resulted from two different tectonic events: one, corresponding to the intrusion of the Late Cretaceous Sintra igneous diapir, and the other the Miocene compressive event, the most important tectonic inversion phase of the Lusitanian Basin. The former are present to the south, southeast and east of the intrusion and within the intrusion itself, affecting the peripheral granites and their contacts with the gabbro-syenite core. These structures comprehend: i) faults and conical fractures striking parallel to the massif boundary, which were intruded by dykes, ii) vertical faults and fractures of two conjugate sets, dextral NNW-SSE and sinistral NNE-SSW. These faults are certainly associated with the E-W striking massif's northwards directed thrust and indicate a N-S oriented horizontal maximum compressive stress. The Miocene compressive event reactivated most of the inherited structures as follows. The NNWSSE faults located on the Sintra southern platform were reactivated as dextral strike slip faults and the E-W thrust along the northern boundary of the massif was also reactivated. This thrust propagated to the east. It also enhanced the asymmetry of the rim-syncline, uplifted the massif and reactivated the NNE-SSW faults as sinistral lateral ramps, which also accommodated vertical throw. The present Tectonic Map of Sintra together with the available geophysical data (MOREIRA, 1984, KULLBERG et al., 1991, SILVA & MIRANDA, 1994) allowed reassessment of the models proposed for the emplacement of the Sintra, Sines and Monchique igneous massifs, which intruded during Late Cretaceous times along the deep dextral NNW-SSE oriented strike slip fault (RIBEIRO et al., 1979; TERRINHA, 1998; TERRINHA & KULLBERG, 1998).

Tectónica da cadeia da Arrábida

Geociências, Museu Nac. Hist. Nat. Univ. Lisboa, nº 2, 35-84

An agent-based evolutionary approach for manufacturing system layout design

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores