Search

This paper introduces a framework for building probabilistic models with subsequential failure transducers. We first show how various types of subsequential transducers commonly used in natural language processing are represented by conditional probabilistic subsequential transducers and probabilistic subsequential failure transducers. Afterwards, we introduce efficient algorithms for composition of conditional probabilistic subsequential transducers with probabilistic subsequential failure transducers and canonization (weight-pushing) of probabilistic subsequential failure transducers. Those algorithms are applicable to many tasks for representing probabilistic models. One such task is the construction of the H C L G weighted transducer used in speech recognition which we describe in detail. At the end, a comparison between the presented H C L G failure weighted transducer and the standard H C L G weighted transducer along with empirical results for HMM-based speech recognition decoding reveal the competitiveness of the presented constructions. [ABSTRACT FROM AUTHOR]

This paper uses multi-sensor data fusion technology to design and develop a multi-sensor based basketball robot's target recognition and positioning system in an unknown environment. We establish the movement model of the basketball robot, and combine the hardware configuration of the basketball robot, analyse the methods of speed control, position control, and direction control, propose a fuzzy obstacle avoidance strategy in the basketball robot movement process, and simulate the obstacle avoidance strategy. The simulation results show that the proposed fuzzy obstacle avoidance strategy is effective. Carry out the experiment of basketball robot target calibration, build the basketball robot monitoring system, and realize data transmission and real-time image processing. Experiments show that the basketball robot can achieve target recognition and positioning tasks in an unknown environment (obstacle comparison rules). It proves the effectiveness and robustness of the proposed following algorithm. It illustrates the effectiveness of the system designed in this paper. [ABSTRACT FROM AUTHOR]

For an m -edge connected simple graph G , finding a spanning tree of G with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if G is planar and the maximal degree of G is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors 5 and 3. Later, they obtained a 3 -approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's O (m) -time 2 -approximation algorithm. We show an alternative simple O (m) -time 2 -approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. [ABSTRACT FROM AUTHOR]

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree 3. We use this result to show that HCYCLE is NP-complete for K 1 , 5 -free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in K 1 , 3 -free and K 1 , 4 -free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems. [ABSTRACT FROM AUTHOR]

A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed and integer , there is a unit disk graph with bounded degree consisting of at least vertices for which the output of the greedy algorithm is no better than times of an optimum solution to the same graph. [ABSTRACT FROM AUTHOR]

For a string w ∈ {0,1, 2,..., d-1}*, let vald(w) denote the integer whose base d representation is the string w and let MSDd(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and Karhumäki [9] studied the problem of computing the leading digit in the ternary representation of 2x ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of AB for given inputs A and B. In this paper, we study this problem from a formal language point of view. Formally, we consider the language Lb,d,j = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSDb(dvalb(w))) = j} (and some related classes of languages) and address the question of whether this and some related languages are context-free. Standard pumping lemma proofs seem to be very difficult for these languages. We present a unified and simple combinatorial technique that shows that these languages are not unambiguous context-free languages. The Benford-Newcomb distribution plays a central role in our proofs. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

In this paper we address the question of synchronizing random automata in the critical settings of almost-group automata. Group automata are automata where all letters act as permutations on the set of states, and they are not synchronizing (unless they have one state). In almost-group automata, one of the letters acts as a permutation on n − 1 states, and the others as permutations. We prove that this small change is enough for automata to become synchronizing with high probability. More precisely, we establish that the probability that a strongly-connected almost-group automaton is not synchronizing is 2 k − 1 − 1 n 2 (k − 1) (1 + o (1)) , for a k -letter alphabet. We also present an efficient algorithm that decides whether a strongly-connected almost-group automaton is synchronizing. For a natural model of computation, we establish a O (k n) worst-case lower bound for this problem (O (n) for the average case), which is almost matched by our algorithm. [ABSTRACT FROM AUTHOR]

The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGESTED CLIQUE model (CCM) [29] of distributed computing. For the Steiner tree problem in the CCM, we consider that each vertex of the input graph is uniquely mapped to a processor and edges are naturally mapped to the links between the corresponding processors. Regarding output, each processor should know whether the vertex assigned to it is in the solution or not and which of its incident edges are in the solution. We present two deterministic distributed approximation algorithms for the Steiner tree problem in the CCM. The first algorithm computes a Steiner tree using Õ (n 1 / 3) rounds and Õ (n 7 / 3) messages for a given connected undirected weighted graph of n nodes. Note here that Õ (⋅) notation hides polylogarithmic factors in n. The second one computes a Steiner tree using O (S + log log n) rounds and O (S m + n 2) messages, where S and m are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of 2 (1 − 1 / ℓ) , where ℓ is the number of leaf nodes in the optimal Steiner tree. For graphs with S = ω (n 1 / 3 log n) , the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with S = õ (n 1 / 3) , the second algorithm outperforms the first one in terms of the round complexity. In fact when S = O (log log n) then the second algorithm achieves a round complexity of O (log log n) and message complexity of Õ (n 2). To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM. [ABSTRACT FROM AUTHOR]

Transducers constitute a fundamental extension of automata. The class of regular word functions has recently emerged as an important class of word-to-word functions, characterized by means of (functional, or unambiguous, or deterministic) two-way transducers, copyless streaming string transducers, and MSO-definable graph transformations. A fundamental result in language theory is Kleene's Theorem, relating finite state automata and regular expressions. Recently, a set of regular function expressions has been introduced and used to prove a similar result for regular word functions, by showing its equivalence with copyless streaming string transducers. In this paper, we propose a direct, simplified and effective translation from unambiguous two-way transducers to regular function expressions extending the Brzozowski and McCluskey algorithm. In addition, our approach allows us to derive a subset of regular function expressions characterizing the (strict) subclass of functional sweeping transducers. [ABSTRACT FROM AUTHOR]

We consider an extension of tree automata on infinite trees that can use equality and disequality constraints between direct subtrees of a node. Recently, it has been shown that the emptiness problem for these kind of automata with a parity acceptance condition is decidable and that the corresponding class of languages is closed under Boolean operations. In this paper, we show that the class of languages recognizable by such tree automata with a Büchi acceptance condition is closed under projection. This construction yields a new algorithm for the emptiness problem, implies that a regular tree is accepted if the language is non-empty (for the Büchi condition), and can be used to obtain a decision procedure for an extension of monadic second-order logic with predicates for subtree comparisons. [ABSTRACT FROM AUTHOR]

A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. This paper addresses a new problem by extending the closed string problem to the k -closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We address the problem of deciding whether or not a given string of length n over an integer alphabet is k -closed and additionally specifying the border resulting in the string being k -closed. Specifically, we present an 𝒪 (k n) -time and 𝒪 (n) -space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results. [ABSTRACT FROM AUTHOR]

In this paper, we introduce some basic measures for insertion-deletion system and matrix insertion-deletion system. These measures are based on the number of variables, the number of productions and the number of symbols in a grammar. We show that with respect to these measures, both the systems are more succinct over context-free grammars in representing certain families of context-free languages. [ABSTRACT FROM AUTHOR]

A classical theme in recursion theory is the question whether for a set A and n given elements x1,...,xn, an oracle machine having access to an oracle B can determine which of the elements xi belong to A. And if yes, how many queries are necessary? Here, B = A is possible and leads to interesting special cases of the general question In the present paper we adapt classical notions in this area of bounded query computations to real number algorithms as formalized by Blum, Shub, and Smale and analyze them in the new framework. Among the results obtained we find: A real version of a non-speedup theorem based on real quantifier elimination, some basic properties about selective real sets, and a way to construct natural terse sets in ℝ by applying the implicit function theorem. The purpose of the paper is on presenting some interesting questions and basic results as an appertizer to intensify research into this direction. [ABSTRACT FROM AUTHOR]

A feedback vertex/arc set (abbreviated as FVS/FAS) of a graph is a subset of the vertices/arcs which contains at least one vertex/arc for every cycle of that graph. A minimum FVS/FAS is an FVS/FAS which contains the smallest number of vertices/arcs. Hsu et al. [11] first proposed an algorithm which can find a minimum FVS in a rotator graph. In this paper, we present a formula for finding an FAS for a rotator graph and prove that the FAS is minimum. This formula can be easily implemented by an efficient algorithm which obtains a minimum FAS in a rotator graph. Finally, we also present a concise formula for finding a minimum FAS in an incomplete rotator graph in this paper. [ABSTRACT FROM AUTHOR]

The existing helmet detection algorithms have disadvantages such as difficulty in detecting occluded targets, small targets, etc. To address those problems, a YOLO V4-based helmet detection improvement algorithm has been proposed. Firstly, the model's backbone structure is improved, and the backbone's multi-scale feature extraction capability is enhanced by using MCM modules with different sized convolutional kernels, the FSM channel attention module is used to guide the model to dynamically focus on the channel features of extracted small targets and obscured target information. Secondly, in order to optimize the model training, the latest loss function Eiou is used to replace Ciou for anchor frame regression prediction to improve the convergence speed and regression accuracy of the model. Finally, a helmet dataset is constructed from this paper, and a K-means clustering algorithm is used to cluster the helmet dataset and select the appropriate a priori candidate frames. The experimental results show that the improved algorithm has a significant improvement in detection accuracy compared with the original YOLO V4 algorithm, and can have a positive detection effect on small targets and obscured targets. [ABSTRACT FROM AUTHOR]

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [ABSTRACT FROM AUTHOR]

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs. [ABSTRACT FROM AUTHOR]

A fundamental problem in music is to classify songs according to their rhythm. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. In this paper, we present an efficient algorithm for locating the maximum-length substring of a music text t that can be covered by a given rhythm r. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a simple, Monte Carlo algorithm for the problem of checking whether a Quantified Boolean Formula (QBF) in Conjunctive Normal Form (CNF), with at most two literals per clause has a model. The term k-CNF is used to describe boolean formulas in CNF, with at most /c literals per clause and the problem of checking whether a given k-CNF formula is satisfiable is called the k-SAT problem. A QBF is a boolean formula, accompanied by a quantifier string which imposes a linear ordering on the variables of that formula. The problem of finding a model for a QBF formula in CNF, with at at most k literals per clause is called the QkSAT problem. The QkSAT problem is PSPACE-complete, for k ≥ 3. However, the Q2SAT problem can be decided in polynomial time; the graph-based procedure, discussed in [1], is the first such algorithm for this problem. This procedure requires the construction of a global implication graph, corresponding to the input formula and searching for certain paths in this graph. Hence the complete set of clauses must be part of the input. We propose an incremental, randomized approach for the Q2SAT problem that is essentially local in nature, in that the complete clausal set need not be provided at any time, in the presence of a verifier. We show that the randomized algorithm can be analyzed as a one-dimensional random walk, with one reflecting barrier and one absorbing barrier. On a Q2SAT instance with in clauses on n variables, our coin-flipping algorithm runs in time O(n² V(m, n)), where V(m, n) is the time required to verify that a given model satisfies the formula. Additionally, if the instance is satisfiable, the probability that our algorithm fails to find a model is less than one half. The design and analysis of a randomized algorithm for a problem, is important from both the theoretical and the practical perspectives. Randomized approaches tend to be simple and elegant, thereby making the process of checking correctness, effortless as well. The randomized approach discussed in this paper lays the groundwork for analyzing a number of problems related to 2CNF formulas and directed graphs. We remark that our work in this paper is the first randomized algorithm for a class of QBFs. [ABSTRACT FROM AUTHOR]

We study hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over a network of processors, and work in a cooperative manner to fulfill various tasks. A hierarchical approach is to group and organize the distributed processes into a logical hierarchy of multiple levels, so as to coordinate the local computation/control activities to improve the overall system performance. It has been proposed as an effective way to solve various problems in distributed computing, such as distributed monitoring, resource scheduling, and network routing. The optimization problem considered in this paper is concerned with finding an optimal hierarchical partition of the processors, so that the total traffic flow over the network is minimized. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting and processing information from all processors. By limiting levels of the hierarchy to two, we will establish the analytically optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed to achieve minimal communication cost (network traffic flow). We will also present and discuss heuristic algorithms for multiple-level hierarchical partitions. [ABSTRACT FROM AUTHOR]

This paper addresses multicasting and broadcasting in undirected WDM networks and QoS extensions of multicasting. It is given an undirected network G=(V, E), with Λ is the set of the available wavelengths in G, and associated with each edge, there is a subset of wavelengths on it. For a multicast request r=(s, D) with a source s and a set D of destinations, it is to find a tree rooted at s including all nodes in D such that the cost of the tree is minimized in terms of the cost of wavelength conversion at nodes and the cost of using wavelength on edges. This paper proves that multicasting in this model of networks is NP-Hard and cannot be approximated within a constant factor, unless P=NP. Furthermore, an auxiliary graph is constructed for the original WDM network, the multicasting is reduced to a group Steiner tree problem on the auxiliary graph and an approximate algorithm based on the group Steiner tree algorithm proposed by M. Charikar et al. with performance ratio of O(log[sup 2](nk) log log(nk) log p) is provided, where k=|Λ| and p=|D∪{s}|. At last, some QoS extensions of multicasting are discussed. [ABSTRACT FROM AUTHOR]

Heterogeneous multiprocessor architectures allow embedded real-time systems to better match computing resources to each application's needs and dynamic workload requirements, thereby providing many opportunities for improved performance with reduced power consumption. Unfortunately, guaranteeing real-time requirements on heterogeneous multiprocessors remains a critical problem due to the lack of appropriate scheduling algorithms and analysis methods. In this paper, we consider EDZL (Earliest Deadline First until Zero-Laxity) for performance asymmetric multiprocessor scheduling. EDZL has been shown to outperform other scheduling policies such as global EDF on identical multiprocessors. We show that EDZL is still effective on performance asymmetric multi-processors, and present an efficient EDZL schedulability test. Experimental results show that EDZL scheduling is able to schedule up to 20% more task sets than global EDF and that our new EDZL schedulability test can accept up to 30% more schedulable task sets than a presently exiting one. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to large autonomous systems. In these models, data are most of the time left unstructured in a container, formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stand in their complexity: each computation step may require a complexity in where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a characterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in for searching reactants, while showing that and that most of the time. [ABSTRACT FROM AUTHOR]

The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower bounds on the conversion of finite automata to regular expressions and vice versa. As an interesting special case also one-unambiguous regular expressions, a sort of a deterministic version of a regular expression, are considered. We also briefly recall the known bounds for the removal of spontaneous transitions ( ε-transitions) on non- ε-free nondeter-ministic devices. Moreover, we report on recent results on the average case descriptional complexity bounds for the conversion of regular expressions to finite automata and new developments on the state elimination algorithm that converts finite automata to regular expressions. [ABSTRACT FROM AUTHOR]

The exchanged crossed cube, denoted by E C Q (s , t) , is a novel interconnection network with fewer edges and smaller diameter compared to other variations of the corresponding hypercube. The linear array, denoted by L n , is one of the most popular topologies in optical networks. This paper addresses the routing and wavelength assignment for realizing E C Q (s , t) communication pattern on wavelength division multiplexing (WDM) optical network L n , where n = s + t + 1. We prove that the congestion for E C Q (s , t) on L n is equal to 2 s + t − 1 + ⌊ 2 t / 3 ⌋ , which is the lower bound of the minimum number of required wavelengths. In addition, an embedding scheme and an optimal wavelength assignment algorithm that achieve this bound are also proposed. [ABSTRACT FROM AUTHOR]

This paper describes a failure scenario in the known self-stabilizing algorithm for knot detection in directed graphs, occurring due to incorrect computation of certain variables. A modified algorithm is proposed, which overcomes the shortcomings of the known algorithm. [ABSTRACT FROM AUTHOR]

The random (2 + p)-SAT model has been proposed [18] to study the possible relation between the 'order' of phase transitions and computational complexity. It was also claimed that there exists pc > 0, such that for p < pc the random (2 + p)-SAT instance behaves like 2-SAT. Later, Achlioptas et al. [3] obtained the first rigorous results that 0.4 ≤ pc ≤ 0.695, the methods they use are the first moment method and the simple Unit-Clause algorithm. In this paper, we try to optimize the local maximality condition of the truth assignments when implementing the first moment method. We prove that the phase transition point of clauses-to-variables ratio r (dependent on p) can be improved. Moreover, we show that the upper bound of pc can be reduced to 0.6846. This fact implies that, for a constant λ < 1, a random (2 + p)-SAT formula with λn 2-clauses and 2.17 n 3-clauses is almost surely unsatisfiable. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

Min-degree constrained minimum spanning tree (md-MST) problem is an NP-hard combinatorial optimization problem seeking for the minimum weight spanning tree in which the vertices are either of degree one (leaf) or at least degree d > 2. md-MST problem is new to the literature and very few studies have been conducted on this problem in deterministic graph. md-MST problem has several appealing real-world applications. Though in realistic applications the graph conditions and parameters are stochastic and vary with time, to the best of our knowledge no work has been done on solving md-MST problem in stochastic graph. This paper proposes a decentralized learning automata-based algorithm for finding a near optimal solution to the md-MST problem in stochastic graph. In this work, it is assumed that the weight associated with the graph edge is random variable with a priori unknown probability distribution. This assumption makes the md-MST problem incredibly harder to solve. The proposed algorithm exploits an intelligent sampling technique avoiding the unnecessary samples by focusing on the edges of the min-degree spanning tree with the minimum expected weight. On the basis of the Martingale theorem, the convergence of the proposed algorithm to the optimal solution is theoretically proven. Extensive simulation experiments are performed on the stochastic graph instances to show the performance of the proposed algorithm. The obtained results are compared with those of the standard sampling method in terms of the sampling rate and solution optimality. Simulation experiments show that the proposed method outperforms the standard sampling method. [ABSTRACT FROM AUTHOR]

In this paper, we study to what extent decidability is connected to universality. A natural context for such a study is provided by the axiomatic theory of computability, automata and algorithms. In Section 2, we introduce necessary concepts, constructions, axioms, postulates, conditions and problems. Section 3 contains the main results of the paper. In particular, it is demonstrated (Theorems 1 and 2) that undecidability of algorithmic problems does not depend on existence of universal algorithms and may be caused by weaker conditions. At the same time, results of Theorems 2 and 3 demonstrate that decidability is incompatible with universality. It is also proved (Theorem 5) that sufficiently big classes of total algorithms/automata, such as the class of all primitive recursive functions, cannot have universal algorithms/automata. [ABSTRACT FROM AUTHOR]

Algorithmic combinatorics on partial words, or sequences of symbols over a finite alphabet that may have some do-not-know symbols or holes, has been developing in the past few years. Applications can be found, for instance, in molecular biology for the sequencing and analysis of DNA, in bio-inspired computing where partial words have been considered for identifying good encodings for DNA computations, and in data compression. In this paper, we focus on two areas of algorithmic combinatorics on partial words, namely, pattern avoidance and subword complexity. We discuss recent contributions as well as a number of open problems. In relation to pattern avoidance, we classify all binary patterns with respect to partial word avoidability, we classify all unary patterns with respect to hole sparsity, and we discuss avoiding abelian powers in partial words. In relation to subword complexity, we generate and count minimal Sturmian partial words, we construct de Bruijn partial words, and we construct partial words with subword complexities not achievable by full words (those without holes). [ABSTRACT FROM AUTHOR]

The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is decidable. In 2009 this decidability problem has been solved positively in [5] by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions. [ABSTRACT FROM AUTHOR]

A general framework of parallel insertion and deletion based on p-schemata is proposed. A p-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of p-schema specifies how to split the word into factors between which the language to be inserted. As its inverse operation, parallel deletion based on the p-schema is defined. Several algebraic properties of these operations such as closure properties of language classes under them are proved. The main contribution of this paper is to propose algorithms to solve language equations involving p-schema-based insertions or deletions based on syntactic congruence. These algorithms not only decide whether a given equation has a solution but construct the set of all of its maximal or minimal solutions. The algorithms are extensible so as to solve some multiple-variables equations and inequalities. Related undecidability results are also presented. [ABSTRACT FROM AUTHOR]

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)-wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for $c < \frac{1}{k}$ and trivial for c ≥ ½, leaving the status of the problem with c in the interval $[\frac{1}{k}, \frac{1}{2})$ widely open. In this paper we show, somehow surprisingly, that ½ is not the threshold for tractability of the perfect matching problem, and prove the existence of an ε > 0 such that the perfect matching problem for the class of hypergraphs H with δ(H) ≥ (½ - ε)|V(H)| is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest. [ABSTRACT FROM AUTHOR]

DNA microarray technology has proven to be an invaluable tool for molecular biologists. Microarrays are used extensively in SNP detection, genomic hybridization, alternative splicing and gene expression profiling. However the manufacturers of the microarrays are often stuck with the problem of minimizing the effects of unwanted illumination (border length minimization (BLM)) which is a hard combinatorial problem. In this paper we prove that the BLM problem on a rectangular grid is NP-hard - this however does not mean the BLM problem on a square grid is NP-hard. We also give the first integer linear programming (ILP) formulation to solve BLM problem optimally. Experimental results indicate that our ILP method produces superior results (both in runtime and cost) compared to the current state of the art algorithms to solve the BLM problem optimally. [ABSTRACT FROM AUTHOR]

The problem of extracting a basis of irredundant motifs from a sequence is considered. In previous work such bases were built incrementally for all suffixes of the input string s in O(n3), where n is the length of s. Faster, non-incremental algorithms have been based on the landmark approach to string searching due to Fischer and Paterson, and exhibit respective time bounds of O(n2log n log|Σ|) and O(|Σ|n2log2 n log log n), with Σ denoting the alphabet. The algorithm by Fischer and Paterson makes crucial use of the FFT, which is impractical with long sequences. The present paper describes an off-line algorithm for binary strings that takes O(n2) time. The algorithm does not need to resort to the FFT and yet its performance is optimal for finite Σ. [ABSTRACT FROM AUTHOR]

This paper explores the phase transitions of the EXPSPACE-complete problems, which mainly focus on the conformant planning problems. The research presents two conformant planning algorithms-CONFORMANT PLAN-NONEXISTENCE algorithm and CONFORMANT PLAN-EXISTENCE algorithm. By analyzing the features of the two algorithms, the phase transition area of the conformant planning problems is obtained. If the number of the operators isn't greater than θub, the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators isn't lower than θlb, the CONFORMANT PLAN-EXISTENCE algorithm can prove that nearly all the conformant planning instances have solutions. The results of the experiments show that there exist phase transitions from a region where almost all the conformant planning instances have no solution to a region where almost all the conformant planning instances have solutions. [ABSTRACT FROM AUTHOR]

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 7.6|Dopt|+1.4, where Dopt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree. [ABSTRACT FROM AUTHOR]

The class of finite Sturmian words consists of words having particularly simple compressed representation, which is a generalization of the Fibonacci recurrence for Fibonacci words. The subword graphs of these words (especially their compacted versions) have a very special regular structure. In this paper we investigate this structure in more detail than in previous papers and show how several syntactical properties of Sturmian words follow from their graph properties. Consequently simple alternative graph-based proofs of several known facts are presented. The very special structure of subword graphs leads also to special easy algorithms computing some parameters of Sturmian words: the number of subwords, the critical factorization point, lexicographically maximal suffixes, occurrences of subwords of a fixed length, and right special factors. These algorithms work in linear time with respect to n, the size of the compressed representation of the standard word, though the words themselves can be of exponential size with respect to n. Some of the computed parameters can be also of exponential size, however we provide their linear size compressed representations. We introduce also a new concept related to standard words: Ostrowski automata. [ABSTRACT FROM AUTHOR]

In order to represent, compute and reason with advanced data types like lists with a fixed length, finite sets or well scoped λ-terms one must go beyond the traditional treatment of data types as being inductive types and, instead, consider them as inductive families, or more precisely Strictly Positive Families (SPFs). We have previously shown that the grammar of strictly positive types (SPT) can be given as an inductively defined family. In the present paper we go one step further an show that the universe of SPFs can be encoded as an SPF. We show that SPFs can be used to represent and compute with a variety of advanced data types and that generic programs can be naturally written over the universe of SPFs. [ABSTRACT FROM AUTHOR]

Screening is an important task to convert a continuous-tone image into a binary image with pure black and white pixels. The main contribution of this paper is to show a new algorithm for cluster-dot screening using a local exhaustive search. Our new algorithm generates 2-cluster, 3-cluster, and 4-cluster binary images, in which all dots have at least 2, 3, and 4 pixels, respectively. The key idea of our new screening method is to repeat a local exhaustive search that finds the best binary pattern in small windows of size k × k in a binary image. The experimental results show that the local exhaustive search produces high quality and sharp cluster-dot binary images. We also present an hardware algorithm to accelerate the computation. Our hardware algorithm for a round of the local exhaustive search runs O(k2) clock cycles while the software implementation runs in O(2k2 w2) time, where (2w + 1) × (2w + 1) is the size of Gaussian filter. Thus, from theoretical point of view, our hardware algorithm achieves a speedup factor of O(w2). To show that our hardware algorithm is practically fast, we have implemented it on an FPGA. Our hardware algorithm achieved a speedup factor of up to 229 over the software implementation. [ABSTRACT FROM AUTHOR]

This paper focuses on the self-stabilizing leader election algorithm of Xu and Srimani [10] that finds a leader in a tree graph. The worst case execution time for this algorithm is O(N4), where N is the number of nodes in the tree. We show that the average execution time for this algorithm, assuming two different scenarios, is much lower than O(N4). In the first scenario, the algorithm assumes an equiprobable daemon and it only privileges a single node at a time. The average execution time for this case is O(N2). For the second case, the algorithm can privilege multiple nodes at a time. We eliminate the daemon from this algorithm by making random choices to avoid interference between neighboring nodes. The execution time for this case is O(N). We also show that for specific tree graphs, these results reduce even more. [ABSTRACT FROM AUTHOR]

As is well-known, Axel Thue constructed an infinite word over a 3-letter alphabet that contains no squares, that is, no nonempty subwords of the form xx. In this paper we consider a variation on this problem, where we try to avoid approximate squares, that is, subwords of the form xx' where |x| = |x'| and x and x' are "nearly" identical. [ABSTRACT FROM AUTHOR]

In this paper two concurrent versions of Brzozowski's deterministic finite automaton (DFA) construction algorithm are developed from first principles, the one being a slight refinement of the other. We rely on Hoare's CSP as our notation. The specifications that are proposed of the Brzozowski algorithm are in terms of the concurrent composition of a number of top-level processes, each participating process itself composed of several other concurrent processes. After considering a number of alternatives, this particular overall architectural structure seemed like a natural and elegant mapping from the sequential algorithm's structure. While we have carefully argued the reasons for constructing the concurrent versions as proposed in the paper, there are of course, a large range of alternative design choices that could be made. There might also be scope for a more fine-grained approach to updating sets or checking for similarity of regular expressions. At this stage, we have chosen to abstract away from these considerations, and leave their exploration for a subsequent step in our research. [ABSTRACT FROM AUTHOR]

In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at leastL. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata. [ABSTRACT FROM AUTHOR]