1,720,984 research outputs found
A representation of recursively enumerable languages by two homomorphisms and a quotient
No full textAbstractA new representation for recursively enumerable languages is presented. It uses a pair of homomorphisms and the left (or right) quotient: For each recursively enumerable language L one can find homomorphisms h1, h2: ∑∗A → ∑∗B, such that w ∈ ∑∗L is a word in L if and only if w =h1(α)h2(α) for some α∈∑+A. (Or, each recursively enumerable language can be given by L = O(h1h2) ∩ ∑∗L, where O(h1h2) is the so-called right overflow languaged defined as O(h1h2) = {h1(x)h2(x); x ∈ ∑∗A}.
Bridging across the log(n) Space Frontier
No full textAbstractThis paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in NSPACE(loglogn)\DSPACE(loglogn). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a functions(n), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a “hardest” fully space constructibles(n)∈O(loglogn), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range betweennand 2d·n
A communication hierarchy of parallel computations
No full textAbstractThe paper extends and generalizes the notion of synchronized alternation, studied in the literature. We show that, though the underlying machine for the synchronized alternation is alternating, the nature of message broadcasting is nondeterministic. Therefore, we introduce a new computational model, the so-called communicating alternation machines; alternating machines equipped with an alternating communication. Then we show that the two-level communication, i.e., existential and universal, can be generalized uniformly arbitrarily many times, giving communication with r communication levels. This allows, among others, to extend the well-known characterization of DLOGSPACE, NLOGSPACE, P, and PSPACE by deterministic, nondeterministic, alternating, and synchronized alternating two-way read-only multihead finite automata. The above characterization represents just the first four members of an infinite hierarchy of multihead automata, representing the entire fundamental complexity hierarchy. The first “new” class added is DEXPTIME, corresponding to the two-level communicating alternation automata
Translation of binary regular expressions into nondeterministic ε-free automata with O(nlogn) transitions
No full textAbstractWe show that every regular expression of size n over a fixed alphabet of s symbols can be converted into a nondeterministic ε-free finite-state automaton with O(snlogn) transitions (edges). In case of binary regular languages, this improves the previous known conversion from O(n(logn)2) transitions to O(nlogn). For the general case with no bound on cardinality of the input alphabet, our conversion yields a better constant factor in the O(n(logn)2) term. The number of states is bounded by O(n)
Magic numbers in the state hierarchy of finite automata
No full textAbstractA number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by n-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers. Actually, most of the numbers is magic in the unary case. As an additional bonus, we also get a new universal lower bound for the conversion of unary d-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below log2d, not even in the best case
An alternating hierarchy for finite automata
No full textAbstractWe study the polynomial state complexity classes 2Σk and 2Πk, that is, the hierarchy of problems that can be solved with a polynomial number of states by two-way alternating finite automata (2Afas) making at most k−1 alternations between existential and universal states, starting in an existential or universal state, respectively. This hierarchy is infinite: for k=2,3,4,…, both 2Σk−1 and 2Πk−1 are proper subsets of 2Σk and of 2Πk, since the conversion of a one-way Σk- or Πk-alternating automaton with n states into a two-way automaton with a smaller number of alternations requires 2n/4−O(k) states. The same exponential blow-up is required for converting a Σk-bounded 2Afa into a Πk-bounded 2Afa and vice versa, that is, 2Σk and 2Πk are incomparable. In the case of Σk-bounded 2Afas, the exponential gap applies also for intersection, while in the case of Πk-bounded 2Afas for union. The same results are established for one-way alternating finite automata.This solves several open problems raised in [C. Kapoutsis, Size complexity of two-way finite automata, in: Proc. Develop. Lang. Theory, in: Lect. Notes Comput. Sci., vol. 5583, Springer-Verlag, 2009, pp. 47–66.
- …
