A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids

A multioperator monoid A\mathcal{A} is a commutative monoid with additional operations on its carrier set. A weighted tree automaton over A\mathcal{A} is a finite state tree automaton of which each transition is equipped with an operation of A\mathcal{A}. We define M-expressions over A\mathcal{A} in the spirit of formulas of weighted monadic second-order logics and, as our main result, we prove that if A\mathcal{A} is absorptive, then the class of tree series recognizable by weighted tree automata over A\mathcal{A} coincides with the class of tree series definable by M-expressions over A\mathcal{A}. This result implies the known fact that for the series over semirings recognizability by weighted tree automata is equivalent with definability in syntactically restricted weighted monadic second-order logic. We prove this implication by providing two purely syntactical transformations, from M-expressions into formulas of syntactically restricted weighted monadic second-order logic, and vice versa.     

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.     

A Fast Algorithm for the Path 2-Packing Problem

Let G be an undirected graph and $\mathcal{T}=\{T_{1},\ldots,T_{k}\}Let G be an undirected graph and T={T₁,?,T_k}\mathcal{T}=\{T_{1},\ldots,T_{k}\} be a collection of disjoint subsets of nodes. Nodes in T ₁∪⋅⋅⋅∪T _k are called terminals, other nodes are called inner. By a T\mathcal{T} -path we mean a path P such that P connects terminals from distinct sets in T\mathcal{T} and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of T\mathcal{T} -paths such that at most two paths in ℘ pass through any node. Our algorithm is purely combinatorial and has the time complexity O(mn ²), where n and m denote the numbers of nodes and edges in G, respectively.     

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.     

Linear-Time Recognition of Helly Circular-Arc Models and Graphs

A circular-arc model ℳ is a circle C together with a collection A\mathcal{A} of arcs of C. If A\mathcal{A} satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n ³). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.     

W-Hierarchies Defined by Symmetric Gates

The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. Here, besides the Boolean connectives we consider connectives such as majority, not-all-equal, and unique. For example, a gate labelled by the majority connective outputs true if more than half of its inputs are true. For any finite set C\mathcal{C} of connectives we construct the corresponding W( C\mathcal{C} )-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W( C\mathcal{C} )-hierarchy coincide levelwise. If C\mathcal{C} only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.     

On one application of computations with oracle

Let P(d) be a program implementing a partial recursive function φ. Let $ \mathcal{O} $ \mathcal{O} _P denote a function defined on the domain of function φ that maps an input data d ₀ onto the path of computation of P on the input d ₀. Let Q(p, d) be a program returning a value if and only if p = $ \mathcal{O} $ \mathcal{O} _P (d), and let the value of the program be Q($ \mathcal{O} $ \mathcal{O} _P (d), d) = P(d). Program Q(p, d), which is totally absurd from the point of view of its practical computation on concrete input data, may be practically useful when it is analyzed by a metaprogram. It is shown in the paper how program Q(p, d) can be used for verification of a postcondition imposed on program P(d). The proposed method was tested on verification tasks for cache coherence protocols and other distributed computing systems.     

An improved algorithm on the content of realizable fuzzy matrices

An n×nn{\times}n fuzzy matrix A is called realizable if there exists an n×tn{\times}t fuzzy matrix B such that A=B\odot B^T,A=B\odot B^{T}, where \odot\odot is the max–min composition. Let r(A)=min{p:A=B\odot B^T, B ? L^n×p}.r(A)={min}\{p:A=B\odot B^{T}, B\in L^{n\times p}\}. Then r(A)r(A) is called the content of A. Since 1982, how to calculate r(A) for a given n×nn{\times}n realizable fuzzy matrix A was a focus problem, many researchers have made a lot of research work. X. P. Wang in 1999 gave an algorithm to find the fuzzy matrix B and calculate r(A) within [r(A)]ⁿ²[r(A)]^{n^{2}} steps. Therefore, to find a simpler algorithm is a problem what we have to consider. This paper makes use of the symmetry of the realizable fuzzy matrix A to simplify the algorithm of content r(A)r(A) based on the work of Wang (Chin Ann Math A 6: 701–706, 1999).     

Decreasing Diagrams and Relative Termination

In this article we use the decreasing diagrams technique to show that a left-linear and locally confluent term rewrite system R\mathcal{R} is confluent if the critical pair steps are relatively terminating with respect to R\mathcal{R}. We further show how to encode the rule-labeling heuristic for decreasing diagrams as a satisfiability problem. Experimental data for both methods are presented.     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

A Geometric Algebra Model for the Image Formation Process of Paracatadioptric Cameras

Omnidirectional vision sensors capture a wide field of view than can benefit many robotic applications. One type of omnidirectional vision sensor is the paracatadioptric. A paracatadioptric sensor combines a parabolic mirror and a camera inducing an orthographic projection. This combination provides a wide field of view while maintaining the single center of projection which is a desirable property of these sensors. Furthermore, lines are projected as circles on the paracatadioptric image plane. In contrast with traditional perspective cameras the image formation process of paracatadioptric sensors is no longer linear. However in this paper we present a model which is able to linearize it. This linearization is based on the fact that the paracatadioptric projection can be represented by a sphere inversion, that belongs to the conformal group Rⁿ\mathcal{R}^{n} which is isomorphic to the Lorentz group in Rⁿ⁺¹\mathcal{R}^{n+1}. Thus a nonlinear conformal transformation can be represented with an equivalent linear Lorenz transformation, which can be represented as a versor in the CGA. Therefore the present model can be applied algebraically not only to points, but also to point-pairs, lines, circles in the same way to all them and in a linear form. The benefits of the proposed method will be reflected on the development of complex applications that use paracatadioptric sensors.     

On the Autoreducibility of Functions

This paper studies the notions of self-reducibility and autoreducibility. Our main result regarding length-decreasing self-reducibility is that any complexity class C\mathcal{C} that has a (logspace) complete language and is closed under polynomial-time (logspace) padding has the property that if all C\mathcal{C} -complete languages are length-decreasing (logspace) self-reducible then C í P\mathcal{C}\subseteq \mathrm {P} (C í L\mathcal {C}\subseteq \mathrm {L} ). In particular, this result applies to NL, NP and PSPACE. We also prove an equivalent of this theorem for function classes (for example, for #P). We also show that for several hard function classes, in particular for #P, it is the case that all their complete functions are deterministically autoreducible. In particular, we show the following result. Let f be a #P parsimonious function with two preimages of 0. We show that there are two FP functions h and t such that for all inputs x we have f(x)=t(x)+f(h(x)), h(x)≠x, and t(x)∈{0,1}. Our results regarding single-query autoreducibility of #P functions can be contrasted with random self-reducibility for which it is known that if a #P complete function were random self-reducible with one query then the polynomial hierarchy would collapse.     

Dependence-space-based attribute reduction in consistent decision tables

This paper proposes a novel approach to attribute reduction in consistent decision tables within the framework of dependence spaces. For a consistent decision table (U,Aè{d}),(U,A\cup \{d\}), an equivalence relation r on the conditional attribute set A and a congruence relation R on the power set of A are constructed, respectively. Two closure operators, T _r and T _R , and two families of closed sets, C_r{\mathcal C}_r and C_R,{\mathcal C}_R, are then constructed with respect to the two equivalence relations. After discussing the properties of C_r{\mathcal C}_r and C_R,{\mathcal C}_R, the necessary and sufficient condition for C_r=C_R{\mathcal C}_r={\mathcal C}_R is obtained and employed to formulate an approach to attribute reduction in consistent decision tables. It is also proved, under the condition C_r=C_R,{\mathcal C}_r={\mathcal C}_R, that a relative reduct is equivalent to a RR-reduction defined by Novotny and Pawlak (Fundam Inform 16:275–287, 1992).     

Delayed theory combination vs. Nelson-Oppen for satisfiability modulo theories: a comparative analysis

Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ .     

The 1-Versus-2 Queries Problem Revisited

The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient algorithm that makes at most 2 queries to a Σ _k ^p -complete language L _k has an efficient simulation that makes at most 1 query to L _k . We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that:

On metric rigidity for some classes of codes

A code C in the n-dimensional metric space $ \mathbb{F}_q^n $ \mathbb{F}_q^n over the Galois field GF(q) is said to be metrically rigid if any isometry I: C → $ \mathbb{F}_q^n $ \mathbb{F}_q^n can be extended to an isometry (automorphism) of $ \mathbb{F}_q^n $ \mathbb{F}_q^n . We prove metric rigidity for some classes of codes, including certain classes of equidistant codes and codes corresponding to one class of affine resolvable designs.     

Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.     

The individual ergodic theorem on the IF-events with product

The ergodic theory and particularly the individual ergodic theorem were studied in many structures. Recently the individual ergodic theorem has been proved for MV-algebras of fuzzy sets (Riečan in Czech Math J 50(125):673–680, 2000; Riečan and Neubrunn in Integral, measure, and ordering. Kluwer, Dordrecht, 1997) and even in general MV-algebras (Jurečková in Int J Theor Phys 39:757–764, 2000). The notion of almost everywhere equality of observables was introduced by Riečan and Jurečková (Int J Theor Phys 44:1587–1597, 2005). They proved that the limit of Cesaro means is an invariant observable for P-observables. In Lendelová (Int J Theor Phys 45(5):915–923, 2006c) showed that the assumption of P-observable can be omitted. In this paper we prove the individual ergodic theorem on family of IF-events and show that each P {\mathcal{P}} -preserving transformation in this family can be expressed by two corresponding P^\flat,P^\sharp {\mathcal{P}}^\flat,{\mathcal{P}}^\sharp -preserving transformations in tribe T. {\mathcal{T}}.     

On some sets of difference sequences of fuzzy numbers

In this paper we define the sequence space w_F(f,p,\Updelta){w}_{{\mathcal{F}}}\left(f,p,\Updelta\right) which is called the space of strongly \Updelta p\Updelta p-Cesàro summable sequences with modulus f. Furthermore the fuzzy Δ-statistically pre-Cauchy sequence is defined and the necessary and sufficient conditions are given for a sequence of fuzzy numbers to be fuzzy \Updelta\Updelta-statistically pre-Cauchy and to be fuzzy \Updelta\Updelta-statistically convergent. Also some relations between w_F(f,p,\Updelta)w_{{\mathcal{F}}}(f,p,\Updelta) and S_F(\Updelta){S}_{{\mathcal{F}}}(\Updelta) are given.