Automata theory based on lattice-ordered semirings

In this paper, definitions of K{\mathcal{K}} automata, K{\mathcal{K}} regular languages, K{\mathcal{K}} regular expressions and K{\mathcal{K}} regular grammars based on lattice-ordered semirings are given. It is shown that K{\mathcal{K}}NFA is equivalent to K{\mathcal{K}}DFA under some finite condition, the Pump Lemma holds if K{\mathcal{K}} is finite, and Ke{{\mathcal{K}}}\epsilonNFA is equivalent to K{\mathcal{K}}NFA. Further, it is verified that the concatenation of K{\mathcal{K}} regular languages remains a K{\mathcal{K}} regular language. Similar to classical cases and automata theory based on lattice-ordered monoids, it is also found that K{\mathcal{K}}NFA, K{\mathcal{K}} regular expressions and K{\mathcal{K}} regular grammars are equivalent to each other when K{\mathcal{K}} is a complete lattice.     

Maximizing the weighted number of just-in-time jobs in?several two-machine scheduling systems

The problem of maximizing the weighted number of just-in-time jobs in a two-machine flow shop scheduling system is known to be NP\mathcal {NP}-hard (Choi and Yoon in J. Shed. 10:237–243, 2007). However, the question of whether this problem is strongly or ordinarily NP\mathcal{NP}-hard remains an open question. We provide a pseudo-polynomial time algorithm to solve this problem, proving that it is NP\mathcal{NP}-hard in the ordinary sense. Moreover, we show how the pseudo-polynomial algorithm can be converted to a fully polynomial time approximation scheme (FPTAS). In addition, we prove that the same problem is strongly NP\mathcal{NP}-hard for both a two-machine job shop scheduling system and a two-machine open shop scheduling system.     

A Two-Step Certified Reduced Basis Method

In this paper we introduce a two-step Certified Reduced Basis (RB) method. In the first step we construct from an expensive finite element “truth” discretization of dimension N{\mathcal{N}} an intermediate RB model of dimension N << NN\ll {\mathcal{N}}. In the second step we construct from this intermediate RB model a derived RB (DRB) model of dimension M≤N. The construction of the DRB model is effected at cost O(N){\mathcal{O}}(N) and in particular at cost independent of N{\mathcal{N}}; subsequent evaluation of the DRB model may then be effected at cost O(M){\mathcal{O}}(M). The DRB model comprises both the DRB output and a rigorous a posteriori error bound for the error in the DRB output with respect to the truth discretization.     

Inverse NP Problems

The inverse problem relative to a verifier V of proofs of membership for a NP language is the problem of deciding, given a set π of proofs, whether or not there exists a string x having exactly π as its set of proofs. In this paper, we study the complexity of inverse problems. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language L cannot be predicted solely from the complexity of L, but rather, is highly dependent upon the choice of verifier used to accept L. In this context, a verifier with a Σ₂ ^p -complete inverse problem is exhibited, giving a new and natural example of a Σ₂ ^p -complete problem.      

Engineering and verifying agent-oriented requirements augmented by business constraints with $${\mathcal{B}}$$-Tropos

We propose B{\mathcal{B}}-Tropos as a modeling framework to support agent-oriented systems engineering, from high-level requirements elicitation down to execution-level tasks. In particular, we show how B{\mathcal{B}}-Tropos extends the Tropos methodology by means of declarative business constraints, inspired by the ConDec graphical language. We demonstrate the functioning of B{\mathcal{B}}-Tropos using a running example inspired by a real-world industrial scenario, and we describe how B{\mathcal{B}}-Tropos models can be automatically formalized in computational logic, discussing formal properties of the resulting framework and its verification capabilities.     

Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays

In this paper, we address a cyclic scheduling problem of finding a periodic schedule with minimal period for the unitary resource constrained cyclic scheduling problem. The main originality is in being able to cope with both precedence delays and complex resource settings which make the problem NP\mathcal{NP}-complete, in general.     

A Dynamic Logic of Agency II: Deterministic $${\mathcal{DLA}}$$ , Coalition Logic,and Game Theory

We continue the work initiated in Herzig and Lorini (J Logic Lang Inform, in press) whose aim is to provide a minimalistic logical framework combining the expressiveness of dynamic logic in which actions are first-class citizens in the object language, with the expressiveness of logics of agency such as STIT and logics of group capabilities such as CL and ATL. We present a logic called DDLA{\mathcal{DDLA}} (Deterministic Dynamic logic of Agency) which supports reasoning about actions and joint actions of agents and coalitions, and agentive and coalitional capabilities. In DDLA{\mathcal{DDLA}} it is supposed that, once all agents have selected a joint action, the effect of this joint action is deterministic. In order to assess DDLA{\mathcal{DDLA}} we prove that it embeds Coalition Logic. We then extend DDLA{\mathcal{DDLA}} with modal operators for agents’ preferences, and show that the resulting logic is sufficiently expressive to capture the game-theoretic concepts of best response and Nash equilibrium.     

A Theory of Hierarchical Consequence and Conditionals

We introduce A{\mathcal{A}} -ranked preferential structures and combine them with an accessibility relation. A{\mathcal{A}} -ranked preferential structures are intermediate between simple preferential structures and ranked structures. The additional accessibility relation allows us to consider only parts of the overall A{\mathcal{A}} -ranked structure. This framework allows us to formalize contrary to duty obligations, and other pictures where we have a hierarchy of situations, and maybe not all are accessible to all possible worlds. Representation results are proved.     

Hardness of Approximating the Closest Vector Problem with Pre-Processing

We show that the pre-processing versions of the closest vector problem and the nearest codeword problem are NP{\mathsf {NP}} -hard to approximate within any constant factor.     

Speeding up simplification of polygonal curves using nested approximations

We develop a top-down multiresolution algorithm (TDMR) to solve iteratively the problem of polygonal curve approximation. This algorithm provides nested polygonal approximations of an input curve. We show theoretically and experimentally that, if the simplification algorithm A{\mathcal{A}} used between any two successive levels of resolution satisfies some conditions, the multiresolution algorithm will have a complexity lower than the complexity of A{\mathcal{A}} applied directly on the input curve to provide the crudest polygonal approximation. In particular, we show that if A{\mathcal{A}} has a O(N ²/K) complexity (the complexity of a reduced search dynamic programming solution approach), where N and K are, respectively, the number of segments in the input curve and the number of segments in the crudest approximation, the complexity of MR is in O(N). We experimentally compare the outcomes of TDMR with those of the optimal full search dynamic programming solution and of classical merge and split approaches. The experimental evaluations confirm the theoretical derivations and show that the proposed approach evaluated on 2D coastal maps either leads to a lower complexity or provides polygonal approximations closer to the initial curves.     

Code obfuscation techniques for metamorphic viruses

This paper deals with metamorphic viruses. More precisely, it examines the use of advanced code obfuscation techniques with respect to metamorphic viruses. Our objective is to evaluate the difficulty of a reliable static detection of viruses that use such obfuscation techniques. Here we extend Spinellis’ result (IEEE Trans. Inform. Theory, 49(1), 280–284, 2003) on the detection complexity of bounded-length polymorphic viruses to metamorphic viruses. In particular, we prove that reliable static detection of a particular category of metamorphic viruses is an -complete problem. Then we empirically illustrate our result by constructing a practical obfuscator which could be used by metamorphic viruses in the future to evade detection.     

Takagi–Sugeno Fuzzy Hopfield Neural Networks for $${\mathcal{H}_{\infty}}$$ Nonlinear System Identification

In this paper, we propose a new H_￥{\mathcal H_\infty} weight learning algorithm (HWLA) for nonlinear system identification via Takagi–Sugeno (T–S) fuzzy Hopfield neural networks with time-delay. Based on Lyapunov stability theory, for the first time, the HWLA for nonlinear system identification is presented to reduce the effect of disturbance to an H_￥{\mathcal{H}_{\infty }} norm constraint. The HWLA can be obtained by solving a convex optimization problem which is represented in terms of linear matrix inequality (LMI). An illustrative example is given to demonstrate the effectiveness of the proposed identification scheme.     

A Dynamic Logic of Agency I: STIT,Capabilities and Powers

The aim of this paper, is to provide a logical framework for reasoning about actions, agency, and powers of agents and coalitions in game-like multi-agent systems. First we define our basic Dynamic Logic of Agency (DLA{\mathcal{DLA}}). Differently from other logics of individual and coalitional capability such as Alternating-time Temporal Logic (ATL) and Coalition Logic, in DLA{\mathcal{DLA}} cooperation modalities for expressing powers of agents and coalitions are not primitive, but are defined from more basic dynamic logic operators of action and (historic) necessity. We show that STIT logic can be reconstructed in DLA{\mathcal{DLA}}. We then extend DLA{\mathcal{DLA}} with epistemic operators, which allows us to distinguish capability and power. We finally characterize the conditions under which agents are aware of their capabilities and powers.     

Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design

In Choi (Quantum Inf Process, 7:193–209, 2008), we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate an optimal complete-graph-minor hardware graph. Given a family F{\mathcal{F}} of graphs, a (host) graph U is called F{\mathcal{F}}-minor-universal if for each graph G in F, U{\mathcal{F}, U} contains a minor-embedding of G. The problem for designing a F{{\mathcal{F}}}-minor-universal hardware graph U _sparse in which F{{\mathcal{F}}} consists of a family of sparse graphs (e.g., bounded degree graphs) is open.     

Relations between Average-Case and Worst-Case Complexity

The consequences of the worst-case assumption NP=P are very well understood. On the other hand, we only know a few consequences of the analogous average-case assumption “NP is easy on average.” In this paper we establish several new results on the worst-case complexity of Arthur-Merlin games (the class AM) under the average-case complexity assumption “NP is easy on average.”

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.     

Rematch: a highly reliable scheduling algorithm on heterogeneous wireless mesh network

In highly dynamic and heterogeneous wireless mesh networks (WMN), link quality will seriously affect network performance. Two challenges hinder us from achieving a highly efficient WMN. One is the channel dynamics. As in real network deployment, channel qualities are changing over time, which would seriously affect network bandwidth and reliability. Existing works are limited to the assumption that link quality values are fixed, and optimal scheduling algorithms are working on the fixed values, which would inevitably suffer from the link quality dynamics. Another challenge is the channel diversity. In single channel wireless networks, channel assignment and scheduling are NP\mathcal{NP} -hard. And in multichannel wireless networks, it could be even harder for higher throughput and efficient scheduling. In this study, we firstly characterize the stochastic behavior on wireless communications in a Markov process, which is based on statistical methodology. Secondly, on exploiting the stochastic behavior on wireless channels, we propose a stochastic programming model in achieving maximized network utilization. Considering the NP\mathcal{NP} -hardness, we propose a heuristic solution for it. The key idea in the proposed algorithm is a two-stage matching process named “Rematch.” Indeed, our solution to the stochastic network scheduling is a cross-layer approach. Also, we have proved that it is 2-approximate to the optimal result. Moreover, extensive simulations have been done, showing the efficiency of “Rematch” in highly dynamic and distributed wireless mesh networks.     

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in ${\mathcal {O}}^{*}(\alpha^{n})$ time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses ${\mathcal {O}}^{*}(1.657^{n})$ time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses ${\mathcal {O}}^{*}(1.6818^{n})$ time and exponential space, and one algorithm that uses ${\mathcal {O}}^{*}(1.8878^{n})$ time and polynomial space.     

VPSPACE and a Transfer Theorem over the Reals

We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class \sf PAR_{\mathbb R}\sf {PAR}_{\mathbb {R}} of decision problems that can be solved in parallel polynomial time over the real numbers collapses to \sfP_{\mathbb R}\sf{P}_{\mathbb {R}}. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate \sfP_{\mathbb R}\sf{P}_{\mathbb {R}} from \sfNP_{\mathbb R}\sf{NP}_{\mathbb {R}}, or even from \sfPAR_{\mathbb R}\sf{PAR}_{\mathbb {R}}.     

The trichotomy of HAVING queries on a probabilistic database

We study the evaluation of positive conjunctive queries with Boolean aggregate tests (similar to HAVING in SQL) on probabilistic databases. More precisely, we study conjunctive queries with predicate aggregates on probabilistic databases where the aggregation function is one of MIN, MAX, EXISTS, COUNT, SUM, AVG, or COUNT(DISTINCT) and the comparison function is one of =, ≠,≥,>,≤, or <. The complexity of evaluating a HAVING query depends on the aggregation function, α, and the comparison function, θ. In this paper, we establish a set of trichotomy results for conjunctive queries with HAVING predicates parametrized by (α, θ). For such queries (without self-joins), one of the following three statements is true: (1) the exact evaluation problem has P{\mathcal P} -time data complexity. In this case, we call the query safe. (2) The exact evaluation problem is \sharpP{{\sharp{\mathcal P}}} -hard, but the approximate evaluation problem has (randomized) P{{\mathcal P}} -time data complexity. More precisely, there exists an FPTRAS for the query. In this case, we call the query apx-safe. (3) The exact evaluation problem is \sharpP{{\sharp{\mathcal P}}} -hard, and the approximate evaluation problem is also hard. We call these queries hazardous. The precise definition of each class depends on the aggregate considered and the comparison function. Thus, we have queries that are (MAX,≥ )-safe, (COUNT,≤ )-apx-safe, (SUM,=)-hazardous, etc. Our trichotomy result is a significant extension of a previous dichotomy result for Boolean conjunctive queries into safe and not safe. For each of the three classes we present novel techniques. For safe queries, we describe an evaluation algorithm that uses random variables over semirings. For apx-safe queries, we describe an FPTRAS that relies on a novel algorithm for generating a random possible world satisfying a given condition. Finally, for hazardous queries we give novel proofs of hardness of approximation. The results for safe queries were previously announced (in Ré, C., Suciu, D. Efficient evaluation of. In: DBPL, pp. 186–200, 2007), but all other results are new.