Search

Abstract: In this paper, we continue our study on the state complexity of combined operations on regular languages. We study the state complexities of , , , and , for regular languages , , . We obtain the exact bounds for these combined operations and show that the state complexities of and are the same as the mathematical compositions of the state complexities of their component individual operations, while, on the other hand, the state complexities of and are lower than the corresponding mathematical compositions. [Copyright &y& Elsevier]

Abstract: Several methods have been developed to construct -free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a -free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods. [Copyright &y& Elsevier]

Abstract: This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals. [Copyright &y& Elsevier]

Abstract: In this paper we develop a version of Algorithmic Information Theory (AIT) based on finite transducers instead of Turing machines; the complexity induced is called finite-state complexity. In spite of the fact that the Universality Theorem (true for Turing machines) is false for finite transducers, the Invariance Theorem holds true for finite-state complexity. We construct a class of finite-state complexities based on various enumerations of the set of finite transducers. In contrast with descriptional complexities (plain, prefix-free) from AIT, finite-state complexity is computable and there is no a priori upper bound for the number of states used for minimal descriptions of arbitrary strings. Upper and lower bounds for the finite-state complexity of arbitrary strings, and for strings of particular types, are given and incompressible strings are studied. [Copyright &y& Elsevier]

Abstract: Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP. [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: It is known that a nontrivial automorphism on a given graph is computed by using any oracle that computes a pair of vertices such that is mapped to by some nontrivial automorphism. In this paper, we consider a weaker oracle acting as follows. For a given graph, the oracle returns a pair of a vertex and a bit with the promise that if it returns , then the vertex is fixed by some nontrivial automorphism, but if it returns , then the vertex is moved by some nontrivial automorphism, provided that the given graph has a nontrivial automorphism. We here note that the oracle may return an arbitrary pair as its answer in case that the given graph has no nontrivial automorphism. We then show a stronger result that such an oracle is still powerful enough to compute a nontrivial automorphism. We also show that a similar result holds for RightGA, a GA-complete problem. We further investigate the computational complexity of computing a partial solution for PrefixGA which is known to be GI-complete. For this problem, we show that, when we consider any oracle similar to one mentioned above, the oracle does not help us to solve PrefixGA unless GI GA. [Copyright &y& Elsevier]

Abstract: In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every , has ith-order scaled -strong dimension 0. We also show that has -dimension and -strong dimension 1. Our results improve previous measure results of Lutz [Almost everywhere high nonuniform complexity, J. Comput. Syst. Sci. 44(2) (1992) 220–258] and dimension results of Hitchcock and Vinodchandran [Dimension, entropy rates, and compression, in: Proc. 19th IEEE Conf. Computational Complexity, 2004, pp. 174–183, J. Comput. Syst. Sci., to appear]. Additionally, we establish a Supergale Dilation Theorem, which extends the martingale dilation technique introduced implicitly by Ambos-Spies, Terwijn, and Zheng [Resource bounded randomness and weakly complete problems, Theoret. Comput. Sci. 172(1–2) (1997) 195–207] and made explicit by Juedes and Lutz [Weak completeness in E and , Theoret. Comput. Sci. 143(1) (1995) 149–158]. [Copyright &y& Elsevier]