We study properties characterized by applying successively a "destructive" rule expressed in first-order logic. the rule says that Points, a(1),...,a(k) of a structure can be removed if they satisfy a certai...
详细信息
ISBN:
(纸本)9783642112652
We study properties characterized by applying successively a "destructive" rule expressed in first-order logic. the rule says that Points, a(1),...,a(k) of a structure can be removed if they satisfy a certain first-order formula. phi(a(1),...,a(k)). the property defined this way by the formula is the set of finite structures such that we are able to obtain the empty structure when applying the rule repeatedly. Many classical properties can be formulated by means of a. "destructive" rule. We do a systematic study of the computational complexity of these properties according to the fragment of first-order logic in which the rule is expressed. We give the list of minimal fragments able to define NP-complete properties and maximal fragments that define only PTIME properties (unless PTIME = NP), depending on the number k of free variables and the quantifier symbols used in the formula. We also study more specifically the case where the formula has one free variable and is universal.
A rising issue in the scientific community entails the identification of temporal patterns in the evolution of the scientific enterprise and the emergence of trendsthat influence scholarly impact. In this direction, ...
详细信息
ISBN:
(纸本)9783319731179;9783319731162
A rising issue in the scientific community entails the identification of temporal patterns in the evolution of the scientific enterprise and the emergence of trendsthat influence scholarly impact. In this direction, this paper investigates the mechanism with which citation accumulation occurs over time and how this affects the overall impact of scientific output. Utilizing data regarding the SOFSEM conference (International conference on currenttrends in theory and practice of computerscience), we study a corpus of 1006 publications withtheir associated authors and affiliations to uncover the effects of collaboration network on the conference output. We proceed to group publications into clusters based on the trajectories they follow in their citation acquisition. Representative patterns are identified to characterize dominant trends of the conference, while exploring phenomena of early and late recognition by the scientific community and their correlation with impact.
Programmers rely on programming idioms, design patterns, and workaround techniques to make up for missing programming language support. Evolving languages often address frequently encountered problems by adding langua...
详细信息
ISBN:
(纸本)9783642112652
Programmers rely on programming idioms, design patterns, and workaround techniques to make up for missing programming language support. Evolving languages often address frequently encountered problems by adding language and library support to subsequent releases. By using new features, programmers can express their intent more directly. As new concerns, such as parallelism or security, arise, early idioms and language facilities can become serious liabilities. Modern code sometimes benefits from optimization techniques not feasible for code that uses less expressive constructs. Manual source code migration is expensive, time-consuming, and prone to errors. In this paper, we present the notion of source code rejuvenation, the automated migration of legacy code and very briefly mention the tools we use to achieve that. While refactoring improves structurally inadequate source code, source code rejuvenation leverages enhanced program language and library facilities by finding and replacing coding patterns that can be expressed through higher-level software abstractions. Raising the level of abstraction benefits software maintainability, security, and performance.
Withthe continuous breakthroughs of unmanned vehicle technology,a increasing number of unmanned vehicles will be added to the current traffic *** will the above situation influence the traffic,and how will we change ...
详细信息
ISBN:
(纸本)9781538629185
Withthe continuous breakthroughs of unmanned vehicle technology,a increasing number of unmanned vehicles will be added to the current traffic *** will the above situation influence the traffic,and how will we change the existing traffic system design program to help unmanned technology to improve people's travel efficiency in a better way,have become urgent problems to be *** this paper,the model of Queuing theory is applied to simulate and calculate the number of lanes of different toll stations,on which basis,the optimal proportional adjustment model of ETC(Electronic Toll Collection) is ***,the results of sensitivity analysis of the model show that it has an excellent robustness and reliability.
Inductive logic programming (ILP) [12] is concerned withthe induction of theories from specific examples and background knowledge, using first-order logic representations for all the three ingredients. In its early d...
详细信息
For a fixed graph H, the H-CONTRACTIBILITY problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. the computational complexity classification of tins problem is s...
详细信息
ISBN:
(纸本)9783642112652
For a fixed graph H, the H-CONTRACTIBILITY problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. the computational complexity classification of tins problem is still open. So far, H has a dominating vertex in all cases known to be polynomially solvable, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-CONTRACTIBILITY is NP-complete. We also present a new class of graphs H for which H-CONTRACTIBILITY is polynomially solvable. Furthermore, we study the (H,v)-CONTRACTIBILITY problem, where v is a vertex of H. the input of this problem is a graph G and an integer k. the question is whether G is H-contractible such that the "bag" of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.
Software Product Line engineering is a popular approach which improves reusability of software in a large number of products that share a common set of features. Feature Models (FMs) are often used to model commonalit...
详细信息
Recent modeling experiments conducted in computational music give evidence that a number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensit...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
Recent modeling experiments conducted in computational music give evidence that a number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensitive interactive systems. Further theoretical developments show that some related notions of higher-dimensional strings can be used as a unifying theme across word or tree automata theory. In this invited paper, we will provide a guided tour of this emerging theory both as an abstract theory and with a view to concrete applications.
Electric field measurements have many scientific applications. their results can be used in atmospheric electricity, optimisation of electric safety, e.g. lightning protection and meteorology. However, a measurement s...
详细信息
ISBN:
(数字)9781665490245
ISBN:
(纸本)9781665490245
Electric field measurements have many scientific applications. their results can be used in atmospheric electricity, optimisation of electric safety, e.g. lightning protection and meteorology. However, a measurement should be performed equally reliably to draw reliable conclusions. In theory and practice, you can find various measurement methods, some used for many years and which can be verified in terms of their accuracy using the possibility of computer simulations. this work contains a field analysis of examples of electric field sensors, based on which a discussion was held and practical conclusions were drawn. Described measurement methodology is often used for measurements of lightning electric field distribution. the article concerns the theory of sensors for measuring electric field and current based on numerical simulations. It can be used both in the problems of the physics of atmospheric lightning discharges and fair-weather electricity. Electric field E and.E measurements are widely described in the literature and have large technical applications. Measurements of the Maxwell current density and its components for thunderstorm electricity and fair weather conditions are associated with many interpretations and technical difficulties. It may touch cases like currents under a thundercloud approaching or currents from distant discharges. For example, Krider and Musser [1] determined the Maxwell current in a situation where Ez(t)=0 (conduction current is that it always vanishes when E is zero). current measurement methods based directly on Gauss or Ampere-Maxwell equations and selecting appropriate sensor surfaces to carry out the integration operation on these surfaces or the paththat bounds that surface may prove difficult or impossible. It needs to choose a unique Gaussian surface to calculate the electric field and a particular Amperian loop to determine the magnetic field and current density.
In this paper we propose a calculus for expressing algorithms for programming languages transformations. We present the type system and operational semantics of the calculus, and we prove that it is type sound. We hav...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
In this paper we propose a calculus for expressing algorithms for programming languages transformations. We present the type system and operational semantics of the calculus, and we prove that it is type sound. We have implemented our calculus, and we demonstrate its applicability with common examples in programming languages. As our calculus manipulates inference systems, our work can, in principle, be applied to logical systems.
暂无评论