Search

This paper deals with the conversion of expressions denoting Hadamard series into weighted rotating automata. We prove that any algorithm converting rational series into one-way weighted automata can be extended to provide an algorithm which achieves our goal. We apply this to define the derivation and the follow automata of a Hadamard expression. Our method may also be used to extend algorithms which perform the inverse conversion, but it is required to enhance the algorithm to fulfil some constraints. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes a four dimensional orthogonal packing and time scheduling problem. The problem differs from the classical packing problems in that the position and orientation of each item in the container can be changed over time. In this way, the four dimensional space–time problem better uses the container time. Also, we consider a general case that all parameters are real numbers, which makes the problems more difficult to solve. This paper proposes an algorithm and proves that the algorithm could solve the problem optimally by a finite number of operations. We say this problem is weak computational, meaning that if there exists a universal machine that could represent real numbers and could do unit arithmetic or logical operation on real numbers in finite time, then the algorithm could find optimal solutions in finite time. This paper also presents a proof of the weak computability over a general case of the three dimensional orthogonal packing problem where all parameters are positive real numbers. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a restricted variant of the scheduling problem, where the machines are the strategic players. For this multi-parameter mechanism design problem, the only known truthful mechanisms use task independent allocation algorithms and only have approximation ratio [N. Nisan, A. Ronen. Algorithmic mechanism design (extended abstract), in: STOC’99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1999. pp. 129–140; A. Mu’alem, M. Schapira, Setting lower bounds on truthfulness: Extended abstract, in: SODA’07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007, pp. 1143–1152; P. Lu, C. Yu, An improved randomized truthful mechanism for scheduling unrelated machines, in: 25th International Symposium on Theoretical Aspects of Computer Science, STACS, 2008, pp. 527–538; P. Lu, C. Yu, Randomized truthful mechanisms for scheduling unrelated machines, in: C.H. Papadimitriou, S. Zhang (Eds.), Proceedings of WINE, in: Lecture Notes in Computer Science, vol. 5385, Springer, 2008, pp. 402–413]. Lavi and Swamy first use the cycle monotone condition and design a 3-approximation truthful mechanism for a two value variant in [R. Lavi, C. Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, in: EC’07: Proceedings of the 8th ACM conference on Electronic commerce, ACM, New York, NY, USA, 2007, pp. 252–261], where the processing time of task on machine , say , can only be either a lower value or a higher value . We consider a generalized variant, where lies in and is a parameter satisfying some condition. We consider two special cases, case A when , and case B when ,, and give randomized truthful mechanisms with approximation ratio for both cases. Based on these two cases’ results, we are also able to deal with the general case of our two-range-values scheduling problem. We use a combination of two mechanisms, which is also a novel method in mechanism design for scheduling problems, and finally we give a randomized truthful mechanism with approximation ratio . Although the generalization seems a little incremental, we actually use a very novel technique in the key step of proving truthfulness for case A, as well as a new mechanism scheme for case B. Besides, the results in this paper are the first truthful mechanisms with constant approximation ratios when a machine (player) can report infinitely possible values, which is quite different from the two value variant, in which only finite values are available. Furthermore, together with Lavi and Swamy’s work, our results suggest that such a task-dependent approach can really do much better for the scheduling unrelated machines problem. [Copyright &y& Elsevier]

In this paper, we consider the weighted online set -multicover problem. In this problem, we have a universe of elements, a family of subsets of with a positive real cost for every , and a “coverage factor” (positive integer) . A subset of elements are presented online in an arbitrary order. When each element is presented, we are also told the collection of all (at least ) sets and their costs to which belongs and we need to select additional sets from if necessary such that our collection of selected sets contains at least sets that contain the element . The goal is to minimize the total cost of the selected sets. 1 [1] Our algorithm and competitive ratio bounds can be extended to the case when a set can be selected at most a prespecified number of times instead of just once; we do not report these extensions for simplicity and also because they have no relevance to the biological applications that motivated our work. In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of [N. Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (1988) 285–318]. This algorithm generalizes and improves some earlier results in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, A general approach to online network optimization problems, in: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 570–579; N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100–105]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general based on the approaches in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100–105]. [Copyright &y& Elsevier]

Abstract: The main focus of this paper is the analysis of a simple randomized scheme for constructing low-weight -connected spanning subgraphs. In this paper, we focus on the metric graph. We use the term metric graph for a complete graph with metric weights. We first show that our scheme gives a simple approximation algorithm to construct a minimum-weight -connected spanning subgraph in a metric graph, an -hard problem. We show that our algorithm gives an approximation ratio of for a metric graph, for a random graph with nodes uniformly randomly distributed in and for a complete graph with random edge weights . We show that our scheme is optimal with respect to the amount of “local information” needed to compute any connected spanning subgraph. We then show that our scheme can be applied to design an efficient distributed algorithm for constructing such an approximate -connected spanning subgraph (for any ) in a point-to-point distributed model, where the processors form a complete network. Our algorithm takes time and an expected number of messages. Our result in conjunction with a result of Korach et al. [E. Korach, S. Moran, S. Zaks, The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, SIAM Journal on Computing 16 (2) (1987) 231–236] implies that the expected message complexity of our algorithm is significantly better than the best distributed algorithm that finds an optimal -connected subgraph. We also show that for geometric instances, our randomized scheme constructs low-degree -connected spanning subgraphs which have maximum degree, with high probability. [Copyright &y& Elsevier]

Abstract: P-printable sets were defined by Hartmanis and Yesha and have been investigated by several researchers. The analogous notion of L-printable sets was defined by Fortnow et al.; both P-printability and L-printability were shown to be related to notions of resource-bounded Kolmogorov complexity. Nondeterministic logspace (NL)-printability was defined by Jenner and Kirsig, but some basic questions regarding this notion were left open. In this paper we answer a question of Jenner and Kirsig by providing a machine-based characterization of the NL-printable sets. In order to relate NL-printability to resource-bounded Kolmogorov complexity, the paper introduces nondeterministic space-bounded Kolmogorov complexity. We present some of the basic properties of this notion of Kolmogorov complexity. Using similar techniques, we investigate relationships among classes between NL and UL. [Copyright &y& Elsevier]

The main purpose of this paper is to present a fast matrix multiplication algorithm taken from the paper of Laderman et al. (Linear Algebra Appl. 162–164 (1992) 557) in a refined compact “analytical” form and to demonstrate that it can be implemented as quite efficient computer code. Our improved presentation enables us to simplify substantially the analysis of the computational complexity and numerical stability of the algorithm as well as its computer implementation. The algorithm multiplies two N × N matrices using O(N2.7760) arithmetic operations. In the case where N = 18·48k, for a positive integer k, the total number of flops required by the algorithm is 4.894N2.7760−16.165N2, which may be compared to a similar estimate for the Winograd algorithm, 3.732N2.8074−5N2 flops, N = 8·2k, the latter being current record bound among all known practical algorithms. Moreover, we present a pseudo-code of the algorithm which demonstrates its very moderate working memory requirements, much smaller than that of the best available implementations of Strassen and Winograd algorithms. For matrices of medium-large size (say, 2000&les;N<10,000) we consider one-level algorithms and compare them with the (multilevel) Strassen and Winograd algorithms. The results of numerical tests clearly indicate that our accelerated matrix multiplication routines implementing two or three disjoint product-based algorithm are comparable in computational time with an implementation of Winograd algorithm and clearly outperform it with respect to working space and (especially) numerical stability. The tests were performed for the matrices of the order of up to 7000, both in double and single precision. [Copyright &y& Elsevier]

Hashiguchi has studied the limitedness problem of distance automata (DA) in a series of paper [(J. Comput System Sci. 24 (1982) 233; Theoret. Comput. Sci. 72 (1990) 27; Theoret. Comput. Sci. 233 (2000) 19)]. The distance of a DA can be limited or unbounded. Given that the distance of a DA is limited, Hashiguchi has proved in Hashiguchi (2000) that the distance of the automaton is bounded by 24n3+n lg(n+2)+n, where n is the number of states. In this paper, we study again Hashiguchi''s solution to the limitedness problem. We have made a number of simplification and improvement on Hashiguchi''s method. We are able to improve the upper bound to 23n3+n lg n+n−1. [Copyright &y& Elsevier]

In this paper, we present an on-line algorithm for adding words (strings) in deterministic directed acyclic word graphs (DAWGs) i.e. acyclic deterministic finite-state automata (DFAs). The proposed algorithm performs optimal insertion, meaning that if applied to a minimal DAWG, the DAWG after the insertion will also be minimal. The time required to add a new word is O(n) with respect to the size of the DAWG. Repetitive application of the proposed insertion algorithm can be used to construct minimal deterministic DAWGs incrementally, although the algorithm is not time-efficient for building minimal DAWGs from a set of words: to build a DAWG of n words this way, O(n2) time is required. However, the algorithm is quite useful in cases where existing minimal DAWGs have to be updated rapidly (e.g. speller dictionaries), since each word insertion traverses only a limited portion of the graph and no additional minimization operation is required. This makes the process very efficient to be used on-line. This paper provides a proof of correctness for the algorithm, a calculation of its time-complexity and experimental results. [Copyright &y& Elsevier]

An important open problem in computational complexity theory is to prove the size of circuits, namely, Boolean circuit lower bounds, necessary to solve explicit problems. We survey learning-theoretic approaches to proofs of Boolean circuit lower bounds in this paper. In particular, we discuss how to prove circuit lower bounds in uniform classes by assuming (or constructing) circuit-learning algorithms in several settings, such as the exact, probably approximately correct (PAC), and statistical query learning models. [ABSTRACT FROM AUTHOR]

In order to run a dataflow with as low cost as possible, it is often faced with deciding which data-sets in a data-set sequence should be stored, with the rest regenerated. The Intermediate Data-set Storage problem arises from this situation. The current best algorithm for this problem takes O ( n 4 ) time. In this paper, we present two improved algorithms for this problem, the first of which can achieve a time complexity O ( n 2 ) , the second of which O ( r n ) , where n is the number of data-sets in a dataflow, r is a numerical number which indicates how large it is for the maximum storage cost to be divided by the minimum computation cost in the dataflow. [ABSTRACT FROM AUTHOR]

This paper provides efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: • The classes of the Boolean hierarchy over level Σ 1 of the dot-depth hierarchy are decidable in NL (previously only the decidability was known). The same remains true if predicates mod d for fixed d are allowed. • If modular predicates for arbitrary d are allowed, then the classes of the Boolean hierarchy over level Σ 1 are decidable. • For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Σ 2 of the Straubing–Thérien hierarchy are decidable in NL. This is the first decidability result for this hierarchy. • The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for NL. • The membership problems for quasi-aperiodic languages and for d -quasi-aperiodic languages are logspace many-one complete for PSPACE. [ABSTRACT FROM AUTHOR]

In this paper, we show the relationship between the two most widely used approaches for the minimization of deterministic finite automata: minimization by split of partitions and minimization by double reversal. Even though the double reversal approach has usually been considered to be unconventional with respect to the more common split approach, we show that any double reversal minimization algorithm can be related to a split minimization algorithm and vice versa. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a two-machine two-stage flow shop problem with flexible tasks is considered. Each job has two tasks: the first task can be processed on either machine, called flexible task, while the second task must be processed on the second machine and canʼt be processed unless the first task is completed. The problem is to determine the assignment of the flexible tasks to the machines for each job, with the objective of minimizing the makespan. We present a fully polynomial time approximation scheme (FPTAS) for the problem. Moreover, we consider the problems with identical jobs and buffer capacity, and present some optimal algorithms for them. For the problems with identical jobs, we find an interesting result: If the buffer is not less than 2, more buffer capacity cannot bring better result. [Copyright &y& Elsevier]

Abstract: In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job’s deterioration effect. Such effect is unexplored in the context of online environment. In this paper we study online single machine scheduling for deteriorating jobs, where jobs arrive over time and become known to any online algorithm on their arrivals. The processing time of each job is a linearly increasing function of its start time. We mainly investigate three online models that minimize makespan, total completion time and maximum delivery time, respectively. For each model we present an optimal online algorithm in competitiveness. [Copyright &y& Elsevier]

Abstract: In this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton defines a coloring of the closed components of the state-pair graph and the minimality of corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states from the state set of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset of (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”. [Copyright &y& Elsevier]

Abstract: Simulation distances are essentially approximations of simulation which provide a measure of the extent by which behaviors in systems are inequivalent. In this paper, we consider the general quantitative model of weighted transition systems, where transitions are labeled with elements of a finite metric space. We study the so-called point-wise and accumulating simulation distances which provide extensions to the well-known Boolean notion of simulation on labeled transition systems. We introduce weighted process algebras for finite and regular behavior and offer sound and (approximate) complete inference systems for the proposed simulation distances. We also settle the algorithmic complexity of computing the simulation distances. [Copyright &y& Elsevier]

Abstract: In this paper, we consider single-machine scheduling problems under the job rejection constraint. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion is minimized, where is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio. [Copyright &y& Elsevier]

Abstract: The - and -methods are the basis for conformance testing from a deterministic finite state machine (DFSM) when the conformance relation considered is equivalence. However, many DFSM applications use only input sequences of limited length. In such cases, the test data only need to establish that the implementation under test produces the specified responses for sequences of length less than or equal to the upper bound . This paper extends the - and -methods to the case in which only bounded sequences are allowed. The methods for bounded sequences are stronger than the originals since test suites for the unbounded case can be obtained as a particular case (in which the upper bound is sufficiently large) from the new formulae. Furthermore, the generalization is not straightforward as it is not sufficient to extract the sequences of length at most from the test suites produced in the unbounded case, or even all prefixes of length at most of the original test sequences. The practicality of the methods is also improved in comparison to the unbounded case: the size of the test suites may be considerably reduced while the complexity of the test generation algorithms remains basically unchanged. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of scheduling with release dates and rejection on a single parallel batching machine, where the jobs have non-identical sizes. Our objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. First, we give a polynomial time approximation scheme (PTAS) for the case where jobs can be split. Then, we propose a -approximation algorithm for the special case with identical release dates. Finally, we present an approximation algorithm for the general problem with worst-case ratio , where is an arbitrarily small constant. [Copyright &y& Elsevier]

Abstract: Kolmogorov complexity and algorithmic probability are defined only up to an additive resp. multiplicative constant, since their actual values depend on the choice of the universal reference computer. In this paper, we analyze a natural approach to eliminate this machine-dependence. Our method is to assign algorithmic probabilities to the different computers themselves, based on the idea that “unnatural” computers should be hard to emulate. Therefore, we study the Markov process of universal computers randomly emulating each other. The corresponding stationary distribution, if it existed, would give a natural and machine-independent probability measure on the computers, and also on the binary strings. Unfortunately, we show that no stationary distribution exists on the set of all computers; thus, this method cannot eliminate machine-dependence. Moreover, we show that the reason for failure has a clear and interesting physical interpretation, suggesting that every other conceivable attempt to get rid of those additive constants must fail in principle, too. However, we show that restricting to some subclass of computers might help to get rid of some amount of machine-dependence in some situations, and the resulting stationary computer and string probabilities have beautiful properties. [Copyright &y& Elsevier]

Abstract: In this paper we study task scheduling problems on identical parallel processors, where each task has unit execution time, and needs either a single processor, or processors concurrently, and it has a release date and a due date. Under the assumption that the release dates and due dates of the -processor tasks are agreeable, we describe a polynomial time algorithm for minimising the number of tardy tasks. In addition, we apply this result for minimising the maximum lateness, and the maximum tardiness. We also discuss the combinatorial background of the polynomial time solvability of all these problems under the ‘agreeable’ assumption. [Copyright &y& Elsevier]

Abstract: We consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. Only one vehicle is available to deliver the jobs to specified customers. The jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. Jobs from different families cannot be transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an -time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we show that the problem is NP-hard and give an -time dynamic programming algorithm, where is the number of jobs, and is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2. [Copyright &y& Elsevier]

Abstract: This paper describes several classes of term rewriting systems (TRS’s), where narrowing has a finite search space and is still (strongly) complete as a mechanism for solving reachability goals. These classes do not assume confluence of the TRS. We also ascertain purely syntactic criteria that suffice to ensure the termination of narrowing, and include several subclasses of popular TRS’s such as right-linear TRS’s, almost orthogonal TRS’s, topmost TRS’s, and left-flat TRS’s. Our results improve and/or generalize previous criteria in the literature regarding narrowing termination. [Copyright &y& Elsevier]

Abstract: Asynchronous programming is a paradigm that supports asynchronous function calls in addition to synchronous function calls. Programs in such a setting can be modeled by automata with counters that keep track of the number of pending asynchronous calls for each function, as well as a call stack for synchronous recursive computation. These programs have the restriction that an asynchronous call is processed only when the call stack is empty. The decidability of the control state reachability problem for such systems was recently established. In this paper, we consider the problems of checking other branching time properties for such systems. Specifically we consider the following problems — termination, which asks if there is an infinite (non-terminating) computation exhibited by the system; control state maintainability, which asks if there is a maximal execution of the system, where all the state visited lie in some “good” set; whether the system can be simulated by a given finite state system; and whether the system can simulate a given finite state system. We present decision algorithms for all these problems. [Copyright &y& Elsevier]

Abstract: 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 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. [Copyright &y& Elsevier]

Abstract: In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages. [Copyright &y& Elsevier]

Abstract: In transfer learning the aim is to solve new learning tasks using fewer examples by using information gained from solving related tasks. Existing transfer learning methods have been used successfully in practice and PAC analysis of these methods have been developed. But the key notion of relatedness between tasks has not yet been defined clearly, which makes it difficult to understand, let alone answer, questions that naturally arise in the context of transfer, such as, how much information to transfer, whether to transfer information, and how to transfer information across tasks. In this paper, we look at transfer learning from the perspective of Algorithmic Information Theory/Kolmogorov complexity theory, and formally solve these problems in the same sense Solomonoff Induction solves the problem of inductive inference. We define universal measures of relatedness between tasks, and use these measures to develop universally optimal Bayesian transfer learning methods. We also derive results in AIT that are interesting by themselves. To address a concern that arises from the theory, we also briefly look at the notion of Kolmogorov complexity of probability measures. Finally, we present a simple practical approximation to the theory to do transfer learning and show that even these are quite effective, allowing us to transfer across tasks that are superficially unrelated. The latter is an experimental feat which has not been achieved before, and thus shows the theory is also useful in constructing practical transfer algorithms. [Copyright &y& Elsevier]

Abstract: The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars. [Copyright &y& Elsevier]

Abstract: The least significant digit first decomposition of integer vectors into words of digit vectors provides a natural way for representing sets of integer vectors by automata. In this paper, the minimal automata representing Presburger sets are proved structurally Presburger: automata obtained by moving the initial state and replacing the accepting condition represent Presburger sets. [Copyright &y& Elsevier]

Abstract: Abstract State Machines (ASMs) were introduced as “a computation model that is more powerful and more universal than standard computation models”, by Yuri Gurevich in 1985. ASMs gained much attention as a specification method. It is extremely flexible because any mathematical structure may serve as a state. Gurevich characterized the expressive power of ASMs in terms of intuitively convincing postulates. The core result of this paper shows that the next-state function M of an Abstract State Machine can be described on a symbolic level, notwithstanding the generality of the model: The successor state of a state is fully specified by the equivalence induced by on the terms over the signature of . Consequently, is computable in case is decidable. Furthermore, this result implies a notion of computability for general structures, e.g. for algorithms operating on real numbers. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done “randomly”. [Copyright &y& Elsevier]

Abstract: We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical states, Theoret. Comput. Sci. 287 (1) (2002) 299–311] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Having a DFA as a component, it trivially recognizes regular languages. We show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. Finally we show the existence of a language that cannot be recognized by a 2OIA but which can be recognized by an space Turing machine. [Copyright &y& Elsevier]

Abstract: The nonstochastic multi-armed bandit problem, first studied by Auer, Cesa-Bianchi, Freund, and Schapire in 1995, is a game of repeatedly choosing one decision from a set of decisions (“experts”), under partial observation: In each round , only the cost of the decision played is observable. A regret minimization algorithm plays this game while achieving sublinear regret relative to each decision. It is known that an adversary controlling the costs of the decisions can force the player a regret growing as in the time . In this work, we propose the first algorithm for a countably infinite set of decisions, that achieves a regret upper bounded by , i.e. arbitrarily close to optimal order. To this aim, we build on the “follow the perturbed leader” principle, which dates back to work by Hannan in 1957. Our results hold against an adaptive adversary, for both the expected and high probability regret of the learner w.r.t. each decision. In the second part of the paper, we consider reactive problem settings, that is, situations where the learner’s decisions impact on the future behaviour of the adversary, and a strong strategy can draw benefit from well chosen past actions. We present a variant of our regret minimization algorithm which has still regret of order at most relative to such strong strategies, and even sublinear regret not exceeding w.r.t. the hypothetical (without external interference) performance of a strong strategy. We show how to combine the regret minimizer with a universal class of experts, given by the countable set of programs on some fixed universal Turing machine. This defines a universal learner with sublinear regret relative to any computable strategy. [Copyright &y& Elsevier]

Abstract: The pattern languages are languages that are generated from patterns, and were first proposed by Angluin as a non-trivial class that is inferable from positive data [D. Angluin, Finding patterns common to a set of strings, Journal of Computer and System Sciences 21 (1980) 46–62; D. Angluin, Inductive inference of formal languages from positive data, Information and Control 45 (1980) 117–135]. In this paper we chronologize some results that developed from the investigations on the inferability of the pattern languages from positive data. [Copyright &y& Elsevier]

Abstract: Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. In this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. We discuss these problems based on reversible logic elements/circuits, reversible Turing machines, reversible cellular automata, and some other related models of reversible computing. [Copyright &y& Elsevier]

We consider a single machine on-line scheduling problem with delivery times. All jobs arrive over time. Each job’s characteristics, such as processing time and delivery time, become known at its arrival time. Once the processing of a job is completed we deliver it to the destination by a vehicle. The objective is to minimize the time by which all jobs have been delivered. In this paper, we assume that all jobs have small delivery times, i.e., for each job , , where and denote the processing time and the delivery time of , respectively. We provide an on-line algorithm with a competitive ratio of , and the result is the best possible. [Copyright &y& Elsevier]

Abstract: In this paper, we prove the decidability of the minimal and maximal reachability problems for multi-priced timed automata, an extension of timed automata with multiple cost variables evolving according to given rates for each location. More precisely, we consider the problems of synthesizing the minimal and maximal costs of reaching a given target location. These problems generalize conditional optimal reachability, i.e., the problem of minimizing one primary cost under individual upper bound constraints on the remaining, secondary, costs, and the problem of maximizing the primary cost under individual lower bound constraints on the secondary costs. Furthermore, under the liveness constraint that all traces eventually reach the goal location, we can synthesize all costs combinations that can reach the goal. The decidability of the minimal reachability problem is proven by constructing a zone-based algorithm that always terminates while synthesizing the optimal cost tuples. For the corresponding maximization problem, we construct two zone-based algorithms, one with and one without the above liveness constraint. All algorithms are presented in the setting of two cost variables and then lifted to an arbitrary number of cost variables. [Copyright &y& Elsevier]

Abstract: Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both the shift number and the number of symbols . This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the -problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of and –for tag systems might be significantly decreased. [Copyright &y& Elsevier]

Abstract: Polygonal differential inclusion systems (SPDI) are a subclass of planar hybrid automata which can be represented by piecewise constant differential inclusions. The reachability problem as well as the computation of certain objects of the phase portrait is decidable. In this paper we show how to compute the viability, controllability and invariance kernels, as well as semi-separatrix curves for SPDIs. We also present the tool SPeeDI+, which implements a reachability algorithm and computes phase portraits of SPDIs. [Copyright &y& Elsevier]

This paper studies the bicriteria problem of scheduling jobs on a batching machine to minimize maximum lateness and makespan simultaneously. A parallel-batching machine is a machine that can handle up to jobs in a batch. The jobs in a batch start and complete at the same time, respectively, and the processing time of a batch is equal to the largest processing time of jobs in the batch. We analyse the unbounded model, where . We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem. [Copyright &y& Elsevier]

Abstract: A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time). [Copyright &y& Elsevier]

Abstract: This paper investigates the semi-online machine covering problems on parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed. We prove that if the total processing time of all jobs or the largest processing time of all jobs is known in advance, the competitive ratios of the optimal algorithms are both . If the total processing time and the largest processing time of all jobs are both known in advance, the competitive ratios of the optimal algorithms are when , and when . [Copyright &y& Elsevier]

Abstract: The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of , where the size of the text is and the size of the pattern is . In this paper we present a new algorithm for the problem whose running time is . [Copyright &y& Elsevier]

Abstract: This paper addresses the problem of generating deterministic -automata for formulas of linear temporal logic, which can be solved by applying well-known algorithms to construct a nondeterministic Büchi automaton for the given formula on which we then apply a determinization algorithm. We study here in detail Safra''s determinization algorithm, present several heuristics that attempt to decrease the size of the resulting automata and report on experimental results. [Copyright &y& Elsevier]

Abstract: The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 2002, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number of a graph G is the minimum cardinality of a power dominating set of G. This problem was proved NP-complete even when restricted to bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for solving the power domination problem in block graphs. As an application of the algorithm, we establish a sharp upper bound for power domination number in block graphs and characterize the extremal graphs. [Copyright &y& Elsevier]

Abstract: In the automata-theoretic approach to model checking we check the emptiness of the product of a system S with an automaton for the complemented specification. This gives rise to two automata-theoretic problems: complementation of word automata, which is used in order to generate , and the emptiness problem, to which model checking is reduced. Both problems have numerous other applications, and have been extensively studied for nondeterministic Büchi word automata (NBW). Nondeterministic generalized Büchi word automata (NGBW) have become popular in specification and verification and are now used in applications traditionally assigned to NBW. This is due to their richer acceptance condition, which leads to automata with fewer states and a simpler underlying structure. In this paper we analyze runs of NGBW and use the analysis in order to describe a new complementation construction and a symbolic emptiness algorithm for NGBW. The complementation construction exponentially improves the best known construction for NGBW and is easy to implement. The emptiness algorithm is almost identical to a known variant of the Emerson–Lei algorithm, and our contribution is the strong relation we draw between the complementation construction and the emptiness algorithm—both naturally follow from the analysis of the runs, which easily implies their correctness. This relation leads to a new certified model-checking procedure, where a positive answer to the model-checking query is accompanied by a certificate whose correctness can be checked by methods independent of the model checker. Unlike certificates generated in previous works on certified model checking, our analysis enables us to generate a certificate that can be checked automatically and symbolically. [Copyright &y& Elsevier]

Abstract: The result, due to Henckell, Margolis, Pin and Rhodes modulo Ash''s solution to the pointlike conjecture, that every finite block group divides a power group, has long been considered to be one of the deepest results in finite semigroup and algebraic automata theory. However, the proof is not constructive. Solving a long-standing problem, we provide in this paper an explicit construction of such a division. We also generalize the result to a large class of pseudovarieties of groups. Local group pseudovarieties are also considered, generalizing (and making constructive) results of Margolis and the second author. Some applications to language theory are mentioned. [Copyright &y& Elsevier]

Abstract: One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound. [Copyright &y& Elsevier]

Abstract: We present in this paper differential approximation results for MIN SET COVER and MIN WEIGHTED SET COVER. We first show that the differential approximation ratio of the natural greedy algorithm for MIN SET COVER is bounded below by and above by , where is the maximum set-cardinality in the MIN SET COVER-instance. Next, we study another approximation algorithm for MIN SET COVER that computes 2-optimal solutions, i.e., solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. We prove that the differential approximation ratio of this second algorithm is bounded below by and that this bound is tight. Finally, we study an approximation algorithm for MIN WEIGHTED SET COVER and provide a tight lower bound of . Our results identically hold for MAX HYPERGRAPH INDEPENDENT SET in both the standard and the differential approximation paradigms. [Copyright &y& Elsevier]