Search results for "Complexity"
showing 10 items of 1094 documents
Improving Interpolants for Linear Arithmetic
2015
Craig interpolation for satisfiability modulo theory formulas have come more into focus for applications of formal verification. In this paper we, introduce a method to reduce the size of linear constraints used in the description of already computed interpolant in the theory of linear arithmetic with respect to the number of linear constraints. We successfully improve interpolants by combining satisfiability modulo theory and linear programming in a local search heuristic. Our experimental results suggest a lower running time and a larger reduction compared to other methods from the literature.
Paths Coloring Algorithms in Mesh Networks
2003
In this paper, we will consider the problem of coloring directed paths on a mesh network. A natural application of this graph problem is WDM-routing in all-optical networks. Our main result is a simple 4-approximation algorithm for coloring line-column paths on a mesh. We also present sharper results when there is a restriction on the path lengths. Moreover, we show that these results can be extended to toroidal meshes and to line-column or column-line paths.
Dynamic 2- and 3-connectivity on planar graphs
1992
We 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 log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).
How self-assembly of amphiphilic molecules can generate complexity in the nanoscale
2015
Abstract Given the importance of nanomaterials and nanostructures in modern technology, in the past decades much effort has been directed to set up efficient bottom up protocols for the piloted self-assembly of molecules. However, molecules are generally disinclined to adopt the desired structural organization because they behave according to their own specific intermolecular interactions. Thus, only some selected classes of chemical compounds are capable to lead to useful self-assembled structures. Amphiphiles, simultaneously possessing polar and apolar moieties within their molecular architecture, can give a wide scenario of possible intermolecular interactions: polar–polar, polar–apolar,…
Anion Recognition by a Bioactive Diureidodecalin Anionophore: Solid-State, Solution, and Computational Studies
2018
Recent work has identified a bis-(p-nitrophenyl)ureidodecalin anion carrier as a promising candidate for biomedical applications, showing good activity for chloride transport in cells yet almost no cytotoxicity. To underpin further development of this and related compounds, a detailed structural and binding investigation is reported. Crystal structures of the transporter as five solvates confirm the diaxial positioning of urea groups while revealing a degree of conformational flexibility. Structures of complexes with Cl−, Br−, NO3 −, SO4 2− and AcO−, supported by computational studies, show how the binding site can adapt to accommodate these anions. 1H NMR binding studies revealed exception…
Multi-disciplinary, Inter-disciplinary, Anti-disciplinary. Transition Knowledges in Design Education
2023
The environmental issues are recently proving to be the center and the connecting element of all the states of crisis, only apparently diversified (energy, political, migration); after the lucid forward-looking analysis of Maldonado in the 70s, the vision proposed in 2019 by the exhibition Broken Nature opens new spaces to the “design hope” activated by design, emphasizing the broad responsibility that the designer must take on contemporary challenges. The complex scenarios of the “transition” (environmental, cultural, productive) are also based on the ability of disciplinary encroachment and on the most radical forms of “anti-disciplinary” innovation, which in some cases opens to design fo…
Reduced complexity models in the identification of dynamical networks: Links with sparsification problems
2009
In many applicative scenarios it is important to derive information about the topology and the internal connections of more dynamical systems interacting together. Examples can be found in fields as diverse as Economics, Neuroscience and Biochemistry. The paper deals with the problem of deriving a descriptive model of a network, collecting the node outputs as time series with no use of a priori insight on the topology. We cast the problem as the optimization of a cost function operating a trade-off between accuracy and complexity in the final model. We address the problem of reducing the complexity by fixing a certain degree of sparsity, and trying to find the solution that “better” satisfi…
Social differentiation and land use at an Early Iron Age “princely seat”: bioarchaeological investigations at the Glauberg (Germany)
2014
Excavations at the late Hallstatt/early La Tene (6th–4th century BC) “princely seat” of the Glauberg (Hesse, Germany) revealed exceptionally furnished graves in monumental mounds, simple inhumations in associated ditches and non-normative burials of up to eight individuals in conical storage pits. The study presented here addresses bioarchaeological characteristics of these burials and their implications for social differentiation and the sphere of influence of the “princely seat”. It includes osteological, aDNA, and multi-isotope analyses of 27 human individuals and faunal remains. One of the outstandingly rich graves (tumulus 1/grave 1) contained the skeleton of a young man (the “prince”)…
Ivory in the Chalcolithic enclosure of Perdigões (South Portugal): the social role of an exotic raw material
2015
AbstractThis article discusses the social role played by ivory and ivory articles in the Perdigoes enclosures (South Portugal) during the Chalcolithic (third millennium bc), in the context of the emergence and development of social complexity on the Iberian Peninsula. Perdigoes is a Portuguese prehistoric site with some of the highest concentrations of ivory objects known in Iberia and with the greatest variety. The contexts, almost exclusively funerary, are discussed along with the results of provenance studies. Comparing the different contexts and the categories of objects made of ivory makes it possible to distinguishing a variety of active social dimensions (such as individual status, g…
‘Adaptive cycles’ and climate fluctuations: a case study from Linear Pottery Culture in western Central Europe
2014
Abstract By applying cycle-based resilience theory the dynamics of the Early Neolithic west-central European Linear Pottery Culture (LBK) are investigated. These are interpreted as resulting from a combination of internal socio-economic processes as well as external environmental parameters. Resilience theory is helpful in understanding periods of increased vulnerability and inherent trends to social complexity. Cycles and threshold levels also help to understand why societies experience periods of increasing fragility and subsequent decline. Results are based on the correlation of a typology and dendrochronology-based archaeological chronology for western LBK and various palaeoclimatic pro…