waashk/dblp huggingface dataset:
a prolongation-projection algorithm for computing the finite real variety of an ideal. we provide a real algebraic symbolic-numeric algorithm for computing the real variety v"r(i) of an ideal i@?r[x], assuming v"r(i) is finite (while v"c(i) could be infinite). our approach uses sets of linear functionals on r[x], vanishing on a given set of polynomials generating i and their prolongations up to a given degree, as well as on polynomials of the real radical ideal ir obtained from the kernel of a suitably defined moment matrix assumed to be positive semidefinite and of maximum rank. we formulate a condition on the dimensions of projections of these sets of linear functionals, which serves as a stopping criterion for our algorithm; this new criterion is satisfied earlier than the previously used stopping criterion based on a rank condition for moment matrices. this algorithm is based on standard numerical linear algebra routines and semidefinite optimization and combines techniques from previous work of the authors together with an existing algorithm for the complex variety.
on the similarity metric and the distance metric. similarity and dissimilarity measures are widely used in many research areas and applications. when a dissimilarity measure is used, it is normally required to be a distance metric. however, when a similarity measure is used, there is no formal requirement. in this article, we have three contributions. first, we give a formal definition of similarity metric. second, we show the relationship between similarity metric and distance metric. third, we present general solutions to normalize a given similarity metric or distance metric.
parallelizing quantum circuits. we present a novel automated technique for parallelizing quantum circuits via the forward and backward translation to measurement-based quantum computing patterns, and analyze the trade off in terms of depth and space complexity. as a result we distinguish a class of polynomial depth circuits that can be parallelized to logarithmic depth while adding only a polynomial number of auxiliary qubits. in particular, we provide for the first time a full characterization of patterns with flow of arbitrary depth, based on the notion of influencing walks and a simple rewriting system on the angles of the measurement. our method provides new insight for constructing parallel circuits and as applications, we demonstrate several classes of circuits that can be parallelized to constant or logarithmic depth. furthermore, we prove a logarithmic separation in terms of quantum depth between the quantum circuit model and the measurement-based model.
on languages generated by asynchronous spiking neural p systems. in this paper, we investigate the languages generated by asynchronous spiking neural p systems. characterizations of finite languages and recursively enumerable languages are obtained by asynchronous spiking neural p systems with extended rules. the relationships of the languages generated by asynchronous spiking neural p systems with regular and non-semilinear languages are also investigated.
on the hopcroft's minimization technique for dfa and dfca. we show that the absolute worst case time complexity for hopcroft's minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de bruijn words. a previous paper by berstel and carton gave the example of de bruijn words as a language that requires o(nlogn) steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a fifo mode for the list of the splitting sets in the algorithm. we refine the previous result by showing that the berstel/carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. we show that the same result is valid also for the case of cover automata and an algorithm based on the hopcroft's method used for minimization of cover automata. we also show that a lifo implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by s. yu.
twin-roots of words and their properties. in this paper we generalize the notion of an @i-symmetric word, from an antimorphic involution, to an arbitrary involution @i as follows: a nonempty word w is said to be @i-symmetric if w=@a@b=@i(@b@a) for some words @a,@b. we propose the notion of @i-twin-roots (x,y) of an @i-symmetric word w. we prove the existence and uniqueness of the @i-twin-roots of an @i-symmetric word, and show that the left factor @a and right factor @b of any factorization of w as w=@a@b=@i(@b@a), can be expressed in terms of the @i-twin-roots of w. in addition, we show that for any involution @i, the catenation of the @i-twin-roots of w equals the primitive root of w. we also provide several characterizations of the @i-twin-rots of a word, for @i being a morphic or antimorphic involution.
state complexity of unique rational operations. for each basic language operation we define its ''unique'' counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. these unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. we study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. equally important, we hope to have provided a generic methodology for estimating their state complexity.
one-shot learners using negative counterexamples and nearest positive examples. as some cognitive research suggests, in the process of learning languages, in addition to overt explicit negative evidence, a child often receives covert explicit evidence in form of corrected or rephrased sentences. in this paper, we suggest one approach to formalization of overt and covert evidence within the framework of one-shot learners via subset and membership queries to a teacher (oracle). we compare and explore general capabilities of our models, as well as complexity advantages of learnability models of one type over models of other types, where complexity is measured in terms of number of queries. in particular, we establish that ''correcting'' positive examples are sometimes more helpful to a learner than just negative (counter) examples and access to full positive data.
on minimal elements of upward-closed sets. upward-closed sets of integer vectors enjoy the merit of having a finite number of minimal elements, which is behind the decidability of a number of petri net related problems. in general, however, such a finite set of minimal elements may not be effectively computable. in this paper, we develop a unified strategy for computing the sizes of the minimal elements of certain upward-closed sets associated with petri nets. our approach can be regarded as a refinement of a previous work by valk and jantzen (in which a necessary and sufficient condition for effective computability of the set was given), in the sense that complexity bounds now become available provided that a bound can be placed on the size of a witness for a key query. the sizes of several upward-closed sets that arise in the theory of petri nets as well as in backward-reachability analysis in automated verification are derived in this paper, improving upon previous decidability results shown in the literature.
state complexity of basic operations on suffix-free regular languages. we investigate the state complexity of basic operations for suffix-free regular languages. the state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. we establish the precise state complexity of catenation, kleene star, reversal and the boolean operations for suffix-free regular languages.
on two open problems of 2-interval patterns. the 2-interval pattern problem, introduced in [stephane vialette, on the computational complexity of 2-interval pattern matching problems theoret. comput. sci. 312 (2-3) (2004) 223-249], models general problems with biological structures such as protein contact maps and macroscopic describers of secondary structures of ribonucleic acids. given a set of 2-intervals d and a model r, the problem is to find a maximum cardinality subset d^' of d such that any two 2-intervals in d^' satisfy r, where r is a subset of relations on disjoint 2-intervals: precedence (
spreading messages. we model a network in which messages spread by a simple directed graph g=(v,e) and a function @a:v->n mapping each v@?v to a positive integer less than or equal to the indegree of v. the graph g represents the individuals in the network and the communication channels between them. an individual v@?v will be convinced of a message when at least @a(v) of its in-neighbors are convinced. suppose we are to convince a message to the individuals by first convincing a subset of individuals, called the seeds, and then let the message spread. we study the minimum number min-seed (g,@a) of seeds needed to convince all individuals at the end. in particular, we prove a lower bound on min-seed (g,@a) and the np-completeness of computing min-seed (g,@a). we also analyze the special case, called the strict-majority scenario, where each individual is convinced of a message when more than half of its in-neighbors are convinced. for the strict-majority scenario, we prove three results. first, we show that with high probability over the erdos-renyi random graphs g(n,p), @w(min{n,1/p}) seeds are needed to convince all individuals at the end. second, if g=(v,e) is undirected, then a set of s uniformly random samples from v convinces no more than an expected s(2|e|+2|v|)|v| individuals at the end. third, in a digraph g=(v,e) with a positive minimum indegree, one can find in polynomial (in |v|) time a set of at most (23/27)|v| seeds convincing all individuals.
new bounds on classical and quantum one-way communication complexity. in this paper we provide new bounds on classical and quantum distributional communication complexity in the two-party, one-way model of communication. in the classical one-way model, our bound extends the well known upper bound of kremer, nisan and ron [i. kremer, n. nisan, d. ron, on randomized one-round communication complexity, in: proceedings of the 27th acm symposium on theory of computing, stoc, 1995, pp. 596-605] to include non-product distributions. let @e@?(0,1/2) be a constant. we show that for a boolean function f:xxy->{0,1} and a non-product distribution @m on xxy, d"@e^1^,^@m(f)=o((i(x:y)+1)@?vc(f)), where d"@e^1^,^@m(f) represents the one-way distributional communication complexity of f with error at most @e under @m; vc(f) represents the vapnik-chervonenkis dimension of f and i(x:y) represents the mutual information, under @m, between the random inputs of the two parties. for a non-boolean function f:xxy->{1,...,k} (k>=2 an integer), we show a similar upper bound on d"@e^1^,^@m(f) in terms of k,i(x:y) and the pseudo-dimension of f^'=deffk, a generalization of the vc-dimension for non-boolean functions. in the quantum one-way model we provide a lower bound on the distributional communication complexity, under product distributions, of a function f, in terms of the well studied complexity measure of f referred to as the rectangle bound or the corruption bound of f. we show for a non-boolean total function f:xxy->z and a product distribution @m on xxy, q"@e"^"3"/"8^1^,^@m(f)=@w(rec"@e^1^,^@m(f)), where q"@e"^"3"/"8^1^,^@m(f) represents the quantum one-way distributional communication complexity of f with error at most @e^3/8 under @m and rec"@e^1^,^@m(f) represents the one-way rectangle bound of f with error at most @e under @m. similarly for a non-boolean partial function f:xxy->z@?{*} and a product distribution @m on xxy, we show, q"@e"^"6"/"("2"@?"1"5"^"4")^1^,^@m(f)=@w(rec"@e^1^,^@m(f)).
a ptas for parallel batch scheduling with rejection and dynamic job arrivals. in the parallel batch scheduling model, a group of jobs can be scheduled together as a batch while the processing time of this batch is the greatest processing time among its members; in the model of scheduling with rejection, any job can be rejected with a corresponding penalty cost added to the objective value. in this paper, we present a ptas for the combined model of the above two scheduling models where jobs arrive dynamically. the objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected ones. our basic approaches are dynamic programming and roundings.
a new heuristic algorithm for the machine scheduling problem with job delivery coordination. in a rapidly changing environment, competition among enterprises has a tendency towards competing between supply chain systems instead of competing between individual companies. traditional scheduling models which only address the sequence of jobs to be processed at the production stage under some criteria are no longer suitable and should be extended to cope with the distribution stage after production. emphasizing on the coordination and integration among various members of a supply chain has become one of the vital strategies for the modern manufacturers to gain competitive advantages. this paper studies the np-hard problem of the two-stage scheduling in which jobs are processed by two parallel machines and delivered to a customer with the objective of minimizing the makespan (p2->d,k=1|v=1,c=z|c"m"a"x). the proposed heuristic algorithm is shown to have a worst-case ratio of 63/40, except for two particular cases.
linear connectivity problems in directed hypergraphs. we introduce a notion of hyperconnection (formally called l-hyperpath) between vertices in a directed hypergraph and relate this notion to existing notions of hyperpaths in directed hypergraphs. we show that some interesting questions in problem domains such as distributed secret sharing and routing in packet filtered networks are basically questions about the existence of l-hyperpaths in directed hypergraphs. we study the computational complexity of problems related to l-hyperpaths and the l-cyclomatic number of directed hypergraphs (the minimum number of hyperedges that need to be deleted to make a directed hypergraph free of l-hypercycles). we prove that the l-hyperpath existence problem, the l-cyclomatic number problem, the minimum l-cyclomatic set problem, and the minimal l-cyclomatic set problem are each complete for the complexity class np, @s"2^p, @p"2^p, and dp, respectively.
optimal tree structures for group key tree management considering insertion and deletion cost. we study the optimal structure for the group broadcast problem where the key tree model is extensively used. the objective is usually to find an optimal key tree to minimize the cost based on certain assumptions. under the assumption that n members arrive in the initial setup period and only member deletions are allowed after that period, previous works show that when only considering the deletion cost, the optimal tree can be computed in o(n^2) time. in this paper, we first prove a semi-balance property for the optimal tree and use it to reduce the running time from o(n^2) to o(loglogn) multiplications of o(logn)-bit integers. then we study the optimal tree structure when insertion cost is also considered. we show that the optimal tree is such a tree where any internal node has degree at most 7 and children of nodes with degree not equal to 2 or 3 are all leaves. based on this result we give a dynamic programming algorithm with o(n^2) time to compute the optimal tree.
cyclic renewal systems. we present three equivalent conditions for a generating set w of a renewal system to generate a maximal monoid in the language of the system. we show that if a code w generates a shift of finite type and satisfies those conditions, then it is cyclic. sufficient conditions are given when the converse holds.
conditional matching preclusion for hypercube-like interconnection networks. the conditional matching preclusion number of a graph with n vertices is the minimum number of edges whose deletion results in a graph without an isolated vertex that does not have a perfect matching if n is even, or an almost perfect matching if n is odd. we develop some general properties on conditional matching preclusion and then analyze the conditional matching preclusion numbers for some hl-graphs, hypercube-like interconnection networks.
parameterized computational complexity of control problems in voting systems. voting systems are common tools in a variety of areas. this paper studies parameterized computational complexity of control of plurality, condorcet and approval voting systems, respectively. the types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. we obtain the following results: (1) constructive control by adding candidates in plurality voting is w[2]-hard with respect to the parameter ''number of added candidates'', (2) destructive control by adding candidates in plurality voting is w[2]-hard with respect to the parameter ''number of added candidates'', (3) constructive control by adding voters in condorcet voting is w[1]-hard with respect to the parameter ''number of added voters'', (4) constructive control by deleting voters in condorcet voting is w[1]-hard with respect to the parameter ''number of deleted voters'', (5) constructive control by adding voters in approval voting is w[1]-hard with respect to the parameter ''number of added voters'', and (6) constructive control by deleting voters in approval voting is w[2]-hard with respect to the parameter ''number of deleted voters''.
exponential inapproximability and fptas for scheduling with availability constraints. we investigate the problems of scheduling n weighted jobs to one or more identical machines with the constraint that the machines may be unavailable in some specified time intervals. the objective is to find a schedule that minimizes the total weighted completion time. we consider both non-resumable and resumable schedules. our first contributions concern approximability. for both resumable problem and non-resumable problem, we show that they cannot be approximated within an exponential factor by any polynomial time algorithm for multiple machines where each of them has an unavailable interval, even if the weight of each job equals to its processing time. additionally, the non-resumable problem is also exponentially inapproximable for a single machine with two or more unavailable intervals. then we develop the first fptass for the problems with a single unavailable interval among all machines. the running time is o(cnlog^dn(1@elogw)^d) for the non-resumable problem, and o(cnlog^dn(1@elogw)^d^+^1) for the resumable problem, where w is the product of the total weight and the total processing time of all jobs, c is the number of machines that are always available and d=6c+12. thus our results give a clear boundary delineating the inapproximable cases and approximable cases. when there is a single machine and w=o(n^l^o^g^n^^^o^^^(^^^1^^^)), our algorithms greatly improve the current results. note that instead of conventional ways of sequentially processing the jobs, our fast schemes process jobs in a divide-and-conquer fashion, which greatly reduces the running time. this may give some insight for some other related problems.
decimations of languages and state complexity. let the words of a language l be arranged in increasing radix order: l={w"0,w"1,w"2,...}. we consider transformations that extract terms from l in an arithmetic progression. for example, two such transformations are even(l)={w"0,w"2,w"4...} and odd(l)={w"1,w"3,w"5,...}. lecomte and rigo observed that if l is regular, then so are even(l), odd(l), and analogous transformations of l. we find good upper and lower bounds on the state complexity of this transformation. we also give an example of a context-free language l such that even(l) is not context-free.
topology on words. we investigate properties of topologies on sets of finite and infinite words over a finite alphabet. the guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. this partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. we consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. we provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.
asynchronous spiking neural p systems. we consider here spiking neural p systems with a non-synchronized (i.e., asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. the additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). that is, we obtain again the equivalence with turing machines (interpreted as generators of sets of (vectors of) numbers). however, this problem remains open for the case of standard spiking neural p systems, whose rules can only produce one spike. on the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete. for these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. however, containment and equivalence are undecidable.
comparison of simple diversity mechanisms on plateau functions. it is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. up to now there is no rigorous analysis pointing out how different diversity mechanisms influence the runtime behavior. we consider evolutionary algorithms that differ from each other in the way they ensure diversity and point out situations where the right mechanism is crucial for the success of the algorithm. the considered evolutionary algorithms either diversify the population with respect to the search points or with respect to function values. investigating simple plateau functions, we show that using the ''right'' diversity strategy makes the difference between an exponential and a polynomial runtime. later on, we examine how the drawback of the ''wrong'' diversity mechanism can be compensated by increasing the population size.
state complexity of power. the number of states in a deterministic finite automaton (dfa) recognizing the language l^k, where l is regular language recognized by an n-state dfa, and k>=2 is a constant, is shown to be at most n2^(^k^-^1^)^n and at least (n-k)2^(^k^-^1^)^(^n^-^k^) in the worst case, for every n>k and for every alphabet of at least six letters. thus, the state complexity of l^k is @q(n2^(^k^-^1^)^n). in the case k=3 the corresponding state complexity function for l^3 is determined as 6n-384^n-(n-1)2^n-n with the lower bound witnessed by automata over a four-letter alphabet. the nondeterministic state complexity of l^k is demonstrated to be nk. this bound is shown to be tight over a two-letter alphabet.