OpenRaiser/Intern-Atlas huggingface dataset:
Universal First-Order Logic is Superfluous for NL, P, NP and coNP
Venue: arXiv cs.LO 2014
Year: 2014

In this work we continue the syntactic study of completeness that began with the works of Immerman and Medina. In particular, we take a conjecture raised by Medina in his dissertation that says if a conjunction of a second-order and a first-order sentences defines an NP-complete problems via fops, then it must be the case that the second-order conjoint alone also defines a NP-complete problem. Although this claim looks very plausible and intuitive, currently we cannot provide a definite answer for it. However, we can solve in the affirmative a weaker claim that says that all ``consistent'' universal first-order sentences can be safely eliminated without the fear of losing completeness. Our methods are quite general and can be applied to complexity classes other than NP (in this paper: to NLSPACE, PTIME, and coNP), provided the class has a complete problem satisfying a certain combinatorial property.
Interval colorings of edges of a multigraph
Venue: arXiv cs.DM 2014
Year: 2014

Let $G=(V_1(G),V_2(G),E(G))$ be a bipartite multigraph, and $R\subseteq V_1(G)\cup V_2(G)$. A proper coloring of edges of $G$ with the colors $1,\ldots,t$ is called interval (respectively, continuous) on $R$, if each color is used for at least one edge and the edges incident with each vertex $x\in R$ are colored by $d(x)$ consecutive colors (respectively, by the colors $1,\ldots,d(x))$, where $d(x)$ is a degree of the vertex $x$. We denote by $w_1(G)$ and $W_1(G)$, respectively, the least and the greatest values of $t$, for which there exists an interval on $V_1(G)$ coloring of the multigraph $G$ with the colors $1,\ldots,t$. In the paper the following basic results are obtained. \textbf{Theorem 2.} For an arbitrary $k$, $w_1(G)\leq k\leq W_1(G)$, there is an interval on $V_1(G)$ coloring of the multigraph $G$ with the colors $1,\ldots,k$. \textbf{Theorem 3.} The problem of recognition of the existence of a continuous on $V_1(G)$ coloring of the multigraph $G$ is $NP$-complete. \textbf{Theorem 4.} If for any edge $(x,y)\in E(G)$, where $x\in V_1(G)$, the inequality $d(x)\geq d(y)$ holds then there is a continuous on $V_1(G)$ coloring of the multigraph $G$. \textbf{Theorem 1.} If $G$ has no multiple edges and triangles, and there is an interval on $V(G)$ coloring of the graph $G$ with the colors $1,\ldots,k$, then $k\leq|V(G)|-1$.
Heterogeneous Speed Profiles in Discrete Models for Pedestrian Simulation
Venue: arXiv cs.MA 2014
Year: 2014

Discrete pedestrian simulation models are viable alternatives to particle based approaches based on a continuous spatial representation. The effects of discretisation, however, also imply some difficulties in modelling certain phenomena that can be observed in reality. This paper focuses on the possibility to manage heterogeneity in the walking speed of the simulated population of pedestrians by modifying an existing multi-agent model extending the floor field approach. Whereas some discrete models allow pedestrians (or cars, when applied to traffic modelling) to move more than a single cell per time step, the present work proposes a maximum speed of one cell per step, but we model lower speeds by having pedestrians yielding their movement in some turns. Different classes of pedestrians are associated to different desired walking speeds and we define a stochastic mechanism ensuring that they maintain an average speed close to this threshold. In the paper we formally describe the model and we show the results of its application in benchmark scenarios. Finally, we also show how this approach can also support the definition of slopes and stairs as elements reducing the walking speed of pedestrians climbing them in a simulated scenario.
Thresholds of absorbing sets in Low-Density-Parity-Check codes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate absorbing sets, responsible of error floors in Low Density Parity Check codes. We look for a concise, quantitative way to rate the absorbing sets' dangerousness. Based on a simplified model for iterative decoding evolution, we show that absorbing sets exhibit a threshold behavior. An absorbing set with at least one channel log-likelihood-ratio below the threshold can stop the convergence towards the right codeword. Otherwise convergence is guaranteed. We show that absorbing sets with negative thresholds can be deactivated simply using proper saturation levels. We propose an efficient algorithm to compute thresholds.
The Scheme of a Novel Methodology for Zonal Division Based on Power Transfer Distribution Factors
Venue: arXiv cs.CE 2014
Year: 2014

One of the methodologies that carry out the division of the electrical grid into zones is based on the aggregation of nodes characterized by similar Power Transfer Distribution Factors (PTDFs). Here, we point out that satisfactory clustering algorithm should take into account two aspects. First, nodes of similar impact on cross-border lines should be grouped together. Second, cross-border power flows should be relatively insensitive to differences between real and assumed Generation Shift Key matrices. We introduce a theoretical basis of a novel clustering algorithm (BubbleClust) that fulfills these requirements and we perform a case study to illustrate social welfare consequences of the division.
Wind Turbine Model and Observer in Takagi-Sugeno Model Structure
Venue: arXiv cs.SY 2014
Year: 2014

Based on a reduced-order, dynamic nonlinear wind turbine model in Takagi-Sugeno (TS) model structure, a TS state observer is designed as a disturbance observer to estimate the unknown effective wind speed. The TS observer model is an exact representation of the underlying nonlinear model, obtained by means of the sector-nonlinearity approach. The observer gain matrices are obtained by means of a linear matrix inequality (LMI) design approach for optimal fuzzy control, where weighting matrices for the individual system states and outputs are included. The observer is tested in simulations with the aero-elastic code FAST for the NREL 5 MW reference turbine, where it shows a stable behaviour both for IEC wind gusts and turbulent wind input.
On Routing-Optimal Network for Multiple Unicasts
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider networks with multiple unicast sessions. Generally, non-linear network coding is needed to achieve the whole rate region of network coding. Yet, there exist networks for which routing is sufficient to achieve the whole rate region, and we refer to them as routing-optimal networks. We identify a class of routing-optimal networks, which we refer to as information-distributive networks, defined by three topological features. Due to these features, for each rate vector achieved by network coding, there is always a routing scheme such that it achieves the same rate vector, and the traffic transmitted through the network is exactly the information transmitted over the cut-sets between the sources and the sinks in the corresponding network coding scheme. We present more examples of information-distributive networks, including some examples from index coding and single unicast with hard deadline constraint.
Introducing E-maintenance 2.0
Venue: arXiv cs.OH 2014
Year: 2014

While research literature is still debating e-maintenance definition, a new reality is emerging in business world confirming the enterprise 2.0 model. Executives are more and more forced to stop running against current trend towards social media and instead envisage harnessing its power within the enterprise. Maintenance can't be an exception for long and has to take advantage of new opportunities created by social technological innovations. In this paper, a combination of pure E perspective and 2.0 perspective is proposed to avoid a lock-in and allow continous evolution of e-maintenance within the new context of business: A combination of data centric models and people oriented applications to form a collaborative environment in order to conceive and achieve global goals of maintenance.New challenges are also to be expected as to the effecient integration of enterprise 2.0 tools within current e-maintenance platforms and futher research work is still to be done in this area.
Infrared face recognition: a comprehensive review of methodologies and databases
Venue: arXiv cs.CV 2014
Year: 2014

Automatic face recognition is an area with immense practical potential which includes a wide range of commercial and law enforcement applications. Hence it is unsurprising that it continues to be one of the most active research areas of computer vision. Even after over three decades of intense research, the state-of-the-art in face recognition continues to improve, benefitting from advances in a range of different research fields such as image processing, pattern recognition, computer graphics, and physiology. Systems based on visible spectrum images, the most researched face recognition modality, have reached a significant level of maturity with some practical success. However, they continue to face challenges in the presence of illumination, pose and expression changes, as well as facial disguises, all of which can significantly decrease recognition accuracy. Amongst various approaches which have been proposed in an attempt to overcome these limitations, the use of infrared (IR) imaging has emerged as a particularly promising research direction. This paper presents a comprehensive and timely review of the literature on this subject. Our key contributions are: (i) a summary of the inherent properties of infrared imaging which makes this modality promising in the context of face recognition, (ii) a systematic review of the most influential approaches, with a focus on emerging common trends as well as key differences between alternative methodologies, (iii) a description of the main databases of infrared facial images available to the researcher, and lastly (iv) a discussion of the most promising avenues for future research.
Branching Bisimilarity Checking for PRS
Venue: arXiv cs.LO 2014
Year: 2014

Recent studies reveal that branching bisimilarity is decidable for both nBPP (normed Basic Parallel Process) and nBPA (normed Basic Process Algebra). These results lead to the question if there are any other models in the hierarchy of PRS (Process Rewrite System) whose branching bisimilarity is decidable. It is shown in this paper that the branching bisimilarity for both nOCN (normed One Counter Net) and nPA (normed Process Algebra) is undecidable. These results essentially imply that the question has a negative answer.
UML Artifacts Reuse: State of the Art
Venue: arXiv cs.SE 2014
Year: 2014

The benefits that can be derived from reusing software include accelerated development, reduced cost, reduced risk and effective use of specialists. Reuse of software artifacts during the initial stages of software development increases reuse benefits, because it allows subsequent reuse of later stage artifacts derived from earlier artifacts. UML is the de facto modeling language used by software developers during the initial stages of software development such as requirements engineering, architectural and detailed design. This survey analyzes previous works on UML artifacts reuse. The analysis considers four perspectives: retrieval method, artifact support, tool support and experiments performed. As an outcome of the analysis, some suggestions for future work on UML artifacts reuse are also provided
Systematic Task Allocation Evaluation in Distributed Software Development
Venue: arXiv cs.SE 2014
Year: 2014

Systematic task allocation to different development sites in global software de- velopment projects can open business and engineering perspectives and help to reduce risks and problems inherent in distributed development. Relying only on a single evaluation criterion such as development cost when distributing tasks to development sites has shown to be very risky and often does not lead to successful solutions in the long run. Task allocation in global software projects is challenging due to a multitude of impact factors and constraints. Systematic allocation decisions require the ability to evaluate and compare task allocation alternatives and to effectively establish customized task allocation practices in an organization. In this article, we present a customizable process for task allocation evaluation that is based on results from a systematic interview study with practitioners. In this process, the relevant criteria for evaluating task allocation alternatives are derived by applying principles from goal-oriented measurement. In addition, the customization of the process is demonstrated, related work and limitations are sketched, and an outlook on future work is given.
Rate-Distortion Properties of Single-Layer Quantize-and-Forward for Two-Way Relaying
Venue: arXiv cs.IT 2014
Year: 2014

The Quantize & Forward (QF) scheme for two-way relaying is studied with a focus on its rate-distortion properties. A sum rate maximization problem is formulated and the associated quantizer optimization problem is investigated. An algorithm to approximately solve the problem is proposed. Under certain cases scalar quantizers maximize the sum rate.
Spectrum Allocation for ICIC Based Picocell
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we analytically study the impact of spectrum allocation scheme in picocells on the coverage probability (CP) of the Pico User (PU), when the macro base stations (MBSs) employ either fractional frequency reuse (FFR) or soft frequency reuse (SFR). Assuming a fixed size for the picocell, the CP expression is derived for a PU present in either a FFR or SFR based deployment, and when the PU uses either the centre or the edge frequency resources. Based on these expressions, we propose two possible frequency allocation schemes for the picocell when FFR is employed by the macrocell. The CP and the average rate expressions for both these schemes are derived, and it is shown that these schemes outperform the conventional scheme where no inter-cell interference coordination (ICIC) is assumed. The impact of both schemes on the macro-user performance is also analysed. When SFR is used by the MBS, it is shown that the CP is maximized when the PU uses the same frequency resources as used by the centre region.
A quantitative analysis of the effect of flexible loads on reserve markets
Venue: arXiv cs.GT 2014
Year: 2014

We propose and analyze a day-ahead reserve market model that handles bids from flexible loads. This pool market model takes into account the fact that a load modulation in one direction must usually be compensated later by a modulation of the same magnitude in the opposite direction. Our analysis takes into account the gaming possibilities of producers and retailers, controlling load flexibility, in the day-ahead energy and reserve markets, and in imbalance settlement. This analysis is carried out by an agent-based approach where, for every round, each actor uses linear programs to maximize its profit according to forecasts of the prices. The procurement of a reserve is assumed to be determined, for each period, as a fixed percentage of the total consumption cleared in the energy market for the same period. The results show that the provision of reserves by flexible loads has a negligible impact on the energy market prices but markedly decreases the cost of reserve procurement. However, as the rate of flexible loads increases, the system operator has to rely more and more on non-contracted reserves, which may cancel out the benefits made in the procurement of reserves.
Limited Feedback-Based Interference Alignment for Interfering Multi-Access Channels
Venue: arXiv cs.IT 2014
Year: 2014

A limited feedback-based interference alignment (IA) scheme is proposed for the interfering multi-access channel (IMAC). By employing a novel performance-oriented quantization strategy, the proposed scheme is able to achieve the minimum overall residual inter-cell interference (ICI) with the optimized transceivers under limited feedback. Consequently, the scheme outperforms the existing counterparts in terms of system throughput. In addition, the proposed scheme can be implemented with flexible antenna configurations.
Generating Extractive Summaries of Scientific Paradigms
Venue: arXiv cs.IR 2014
Year: 2014

Researchers and scientists increasingly find themselves in the position of having to quickly understand large amounts of technical material. Our goal is to effectively serve this need by using bibliometric text mining and summarization techniques to generate summaries of scientific literature. We show how we can use citations to produce automatically generated, readily consumable, technical extractive summaries. We first propose C-LexRank, a model for summarizing single scientific articles based on citations, which employs community detection and extracts salient information-rich sentences. Next, we further extend our experiments to summarize a set of papers, which cover the same scientific topic. We generate extractive summaries of a set of Question Answering (QA) and Dependency Parsing (DP) papers, their abstracts, and their citation sentences and show that citations have unique information amenable to creating a summary.
Lifted Variable Elimination: Decoupling the Operators from the Constraint Language
Venue: arXiv cs.AI 2014
Year: 2014

Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once per group, as opposed to once per variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference use specific languages for (in)equality constraints, which often have limited expressivity. In this article, we decouple lifted inference from the constraint language. We define operators for lifted inference in terms of relational algebra operators, so that they operate on the semantic level (the constraints extension) rather than on the syntactic level, making them language-independent. As a result, lifted inference can be performed using more powerful constraint languages, which provide more opportunities for lifting. We empirically demonstrate that this can improve inference efficiency by orders of magnitude, allowing exact inference where until now only approximate inference was feasible.
Identifying the Class of Maxi-Consistent Operators in Argumentation
Venue: arXiv cs.AI 2014
Year: 2014

Dung's abstract argumentation theory can be seen as a general framework for non-monotonic reasoning. An important question is then: what is the class of logics that can be subsumed as instantiations of this theory? The goal of this paper is to identify and study the large class of logic-based instantiations of Dung's theory which correspond to the maxi-consistent operator, i.e. to the function which returns maximal consistent subsets of an inconsistent knowledge base. In other words, we study the class of instantiations where very extension of the argumentation system corresponds to exactly one maximal consistent subset of the knowledge base. We show that an attack relation belonging to this class must be conflict-dependent, must not be valid, must not be conflict-complete, must not be symmetric etc. Then, we show that some attack relations serve as lower or upper bounds of the class (e.g. if an attack relation contains canonical undercut then it is not a member of this class). By using our results, we show for all existing attack relations whether or not they belong to this class. We also define new attack relations which are members of this class. Finally, we interpret our results and discuss more general questions, like: what is the added value of argumentation in such a setting? We believe that this work is a first step towards achieving our long-term goal, which is to better understand the role of argumentation and, particularly, the expressivity of logic-based instantiations of Dung-style argumentation frameworks.
Reasoning about Explanations for Negative Query Answers in DL-Lite
Venue: arXiv cs.AI 2014
Year: 2014

In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for Description Logics, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for instance and conjunctive query answering over DL-Lite ontologies by adopting abductive reasoning; that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning tasks we consider existence and recognition of an explanation, and relevance and necessity of a given assertion for an explanation. We characterize the computational complexity of these problems for arbitrary, subset minimal, and cardinality minimal explanations.
Optimizing SPARQL Query Answering over OWL Ontologies
Venue: arXiv cs.DB 2014
Year: 2014

The SPARQL query language is currently being extended by the World Wide Web Consortium (W3C) with so-called entailment regimes. An entailment regime defines how queries are evaluated under more expressive semantics than SPARQLs standard simple entailment, which is based on subgraph matching. The queries are very expressive since variables can occur within complex concepts and can also bind to concept or role names. In this paper, we describe a sound and complete algorithm for the OWL Direct Semantics entailment regime. We further propose several novel optimizations such as strategies for determining a good query execution order, query rewriting techniques, and show how specialized OWL reasoning tasks and the concept and role hierarchy can be used to reduce the query execution time. For determining a good execution order, we propose a cost-based model, where the costs are based on information about the instances of concepts and roles that are extracted from a model abstraction built by an OWL reasoner. We present two ordering strategies: a static and a dynamic one. For the dynamic case, we improve the performance by exploiting an individual clustering approach that allows for computing the cost functions based on one individual sample from a cluster. We provide a prototypical implementation and evaluate the efficiency of the proposed optimizations. Our experimental study shows that the static ordering usually outperforms the dynamic one when accurate statistics are available. This changes, however, when the statistics are less accurate, e.g., due to nondeterministic reasoning decisions. For queries that go beyond conjunctive instance queries we observe an improvement of up to three orders of magnitude due to the proposed optimizations.