Search results for "A* algorithm"
showing 10 items of 2538 documents
Nondeterministic Moore automata and Brzozowski's minimization algorithm
2012
AbstractMoore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. We propose an algorithm that is a variant of Brzozowski’s minimization algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice. Moreover, we explore more general classes of NMA and analyze the applicability of the algorithm. For some of such classes the algorith…
Standard Sturmian words and automata minimization algorithms
2015
The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-determ…
Nondeterministic Moore Automata and Brzozowski’s Algorithm
2011
Moore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. In this paper we propose an algorithm that is a variant of Brzozowski's algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.
On Extremal Cases of Hopcroft’s Algorithm
2009
In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different sequences of refinements of the set of the states that lead to the final partition. We find an infinite family of binary automata for which such a process is unique. Some recent papers (cf. [3,7,1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated to circular words. However, automata minimization can be achieved also in linear time when the alphabet has only one letter (cf. [14]), so in …
Minimal nontrivial space complexity of probabilistic one- way turing machines
2005
Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].
The Descriptive Complexity Approach to LOGCFL
1999
Building upon the known generalized-quantifier-based firstorder characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's "hardest contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes
2005
The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
New Encodings of Pseudo-Boolean Constraints into CNF
2009
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
A genetic system based on simulated crossover of sequences of two-bit genes
2006
AbstractWe introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state);(2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials);(3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O(m+l), wh…