Search

We study the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the Boolean operations, concatenation, and Kleene star. We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Our constructions rely on the fact that minimal unary NFAs with limited nondeterminism can be found in Chrobak normal form for most measures of nondeterminism. The measures of nondeterminism which are considered here with the above property are tree width, advice, and trace. [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 investigation of automata and languages defined over a one letter alphabet shows interesting differences with respect to the case of alphabets with at least two letters. Probably, the oldest example emphasizing one of these differences is the collapse of the classes of regular and context-free languages in the unary case (Ginsburg and Rice, 1962). Many differences have been proved concerning the state costs of the simulations between different variants of unary finite state automata (Chrobak, 1986, Mereghetti and Pighizzini, 2001). We present an overview of these results. Because important connections with fundamental questions in space complexity, we give emphasis to unary two-way automata. Furthermore, we discuss unary versions of other computational models, as probabilistic automata, one-way and two-way pushdown automata, even extended with auxiliary workspace, and multi-head automata. [ABSTRACT FROM AUTHOR]

We consider the model of one-way automata with quantum and classical states (QCFAs) introduced in [28]. We show, by a direct approach, that QCFAs with isolated cut-point accept regular languages only, thus characterizing their computational power. Concerning descriptional power, we quickly overview a size lower bound for QCFAs accepting regular languages, and address its optimality. Then, we explicitly build QCFAs accepting the word quotients and inverse homomorphic images of languages accepted by given QCFAs with isolated cut-point, maintaining the same cut-point, isolation, and only polynomially increasing the size. [ABSTRACT FROM AUTHOR]

The state complexity of basic operations on regular languages considering complete deterministic finite automata (DFA) has been extensively studied in the literature. But, if incomplete DFAs are considered, transition complexity is also a significant measure. In this paper we study the incomplete (deterministic) state and transition complexity of some operations for regular and finite languages. For regular languages we give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al. For finite languages, we correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right operand is larger than the left one. We also present some experimental results to test the behavior of those operations on the average case, and we conjecture that for many operations and in practical applications the worst-case complexity is seldom reached. [ABSTRACT FROM AUTHOR]

In the late nineteen sixties it was observed that the r.e. languages form an infinite proper hierarchy based on the size of the Turing machines that accept them. We examine the fundamental position of the finite languages and their complements in the hierarchy. We show that for every finite language L one has that L, for some where m is the length of the longest word in L, c is the cardinality of L, and . If , then for some . We also prove that for every n, there is a finite language Ln with such that but Ln, for some . Several further results are shown that how the hierarchy can be separated by increasing chains of finite languages. The proofs make use of several auxiliary results for Turing machines with advice. [ABSTRACT FROM AUTHOR]

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh's theorem enables us to represent any semilinear set as a pushdown automaton (PDA). We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh's theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words. [ABSTRACT FROM AUTHOR]

Let L/ p o l y and N L be the standard complexity classes, of languages recognizable in logarithmic space by Turing machines which are deterministic with polynomially-long advice and nondeterministic without advice, respectively. We recast the question whether $\mathsf {L}/\mathsf {poly}~{\supseteq }~{\mathsf {NL}}$ in terms of deterministic and nondeterministic two-way finite automata ( 2dfas and 2nfas). We prove it equivalent to the question whether every s-state unary 2nfa has an equivalent poly( s)-state 2dfa, or whether a poly( h)-state 2dfa can check accessibility in h-vertex graphs (even under unary encoding) or check two-way liveness in h-tall, h-column graphs. This complements two recent improvements of an old theorem of Berman and Lingas. On the way, we introduce new types of reductions between regular languages (even unary ones), use them to prove the completeness of specific languages for two-way nondeterministic polynomial size, and propose a purely combinatorial conjecturethat implies $\mathsf {L}/\mathsf {poly}~{\nsupseteq }~\mathsf {NL}$. [ABSTRACT FROM AUTHOR]

In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the question has been answered only for particular cases, while it remains open in general, the best upper bound currently known being exponential. We present a new approach in which unrestricted nondeterministic automata are simulated by deterministic models extending two-way deterministic automata, paying only a polynomial increase of size. Indeed, we study the costs of the conversions of nondeterministic automata into some variants of one-tape deterministic Turing machines working in linear time; namely Hennie machines, weight-reducing Turing machines, and weight-reducing Hennie machines. All these variants are known to share the same computational power: they characterize the class of regular languages. [ABSTRACT FROM AUTHOR]

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2 Θ ( n 2 ) states (B. von Braunmühl and R. Verbeek, 1983 [8] ), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4] ). This paper demonstrates that the same worst-case 2 Θ ( n 2 ) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2 Θ ( n 2 ) , and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2 Θ ( n 2 ) . [ABSTRACT FROM AUTHOR]

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥⃒ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages. [ABSTRACT FROM AUTHOR]

The question of the state-size cost for simulation of two-way nondeterministic automata ( 2 nfa s) by two-way deterministic automata ( 2 dfa s) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2 dfa s (e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2 nfa s. Here we use an opposite approach, increasing the power of 2 dfa s to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2 dfa s. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2 nfa s and 2 dfa s can be obtained only for unrestricted 2 nfa s using capabilities beyond the proposed new model. As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2 dfa s would imply L ≠ NL . In the same way, the alternating version of these machines is related to L = ? NL = ? P , the classical computational complexity problems. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. KLÍMA, L. POLÁK: On biautomata. RAIRO - Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages. [ABSTRACT FROM AUTHOR]

Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to a single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d ≥ 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schützenberger representation for contextfree languages, we present a new conversion from context-free languages into 2-limited automata. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity of deterministic one-way multi-head finite automata accepting unary languages. It is known that in this case the languages accepted are regular. Thus, we study the increase of the number of states when an n-state k-head finite automaton is simulated by a classical (one-head) deterministic or nondeterministic finite automaton. In the former case upper and lower bounds that are tight in the order of magnitude are shown. For the latter case we obtain an upper bound of O(n2k) and a lower bound of Ω(nk) states. We investigate also the costs for the conversion of one-head nondeterministic finite automata to deterministic k-head finite automata, that is, we trade nondeterminism for heads. In addition, we study how the conversion costs vary in the special case of finite and, in particular, of singleton unary lanuages. Finally, as an application of the simulation results, we show that decidability problems for unary deterministic k-head finite automata such as emptiness or equivalence are LOGSPACE-complete. [ABSTRACT FROM AUTHOR]

We study the descriptional cost of removing nondeterminism in constant height pushdown automata--i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs by sweeping 2DFAs and one-way nondeterministic finite automata (1NFAs) as well as the simulation of sweeping 2DFAs by 1NFAs. In all cases exponential lower bounds on the number of states are obtained for languages over an alphabet with at most four letters. Finally, a procedure for deciding obliviousness of an arbitrary 2DFA is given and, moreover, the problem is shown to be PSPACE-complete. [ABSTRACT FROM AUTHOR]

We compare the descriptional power of quantum finite automata with control language ( qfc s) and deterministic finite automata ( dfa s). By suitably adapting Rabin's technique, we show how to convert any given qfc to an equivalent dfa , incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfc s, which is logarithmic in the size of equivalent minimal dfa s. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature. [ABSTRACT FROM AUTHOR]

Abstract: Nowadays, increasing attention is being given to the study of the descriptional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic average-case results for several ε-NFA constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the ε-NFA constructions approaches the corresponding ε-free NFA construction, asymptotically and on average. [Copyright &y& Elsevier]

The restarting automaton was inspired by the technique of 'analysis by reduction' from linguistics. A restarting automaton processes a given input word through a sequence of cycles. In each cycle the current word on the tape is scanned from left to right and a single local simplification (a rewrite) is executed. One of the essential parameters of a restarting automaton is the size of its read/write window. Here we study the impact of the window size on the descriptional complexity of several types of deterministic and nondeterministic restarting automata. For all k ≥ 4, we show that the savings in the economy of descriptions of restarting automata that can only delete symbols but not rewrite them (that is, the so-called R- and RR-automata) cannot be bounded by any recursive function, when changing from window size k to window size k + 1. This holds for deterministic as well as for nondeterministic automata, and for k ≥ 5, it even holds for the stateless variants of these automata. However, the trade-off between window sizes two and one is recursive for deterministic devices. In addition, a polynomial upper bound is given for the trade-off between RRWW-automata with window sizes k + 1 and k for all k ≥ 2. [ABSTRACT FROM AUTHOR]

Abstract: We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view. We prove that for each one-way nondeterministic automaton with n states there exist Parikh equivalent one-way and two-way deterministic automata with and states, respectively, where is a polynomial. Furthermore, these costs are tight. In contrast, if all the words accepted by the given automaton contain at least two different letters, then a Parikh equivalent one-way deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with h variables there exist Parikh equivalent one-way and two-way deterministic automata with and states, respectively. Even these bounds are tight. [Copyright &y& Elsevier]

The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same power of one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question of the costs, in the number of the states, of the simulations of one-way and two-way non-deterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. In spite of all attempts to solve it, this question is still open. In the last ten years the problem of Sakoda and Sipser was widely reconsidered and many new results related to it have been obtained. In this work we discuss some of them. In particular, we focus on the restriction to the unary case, namely the case of automata defined over the one letter input alphabet, and on the connections with open questions in space complexity. [ABSTRACT FROM AUTHOR]

Abstract: We investigate finite-turn pushdown automata (PDAs) from the point of view of descriptional complexity. It is known that such automata accept exactly the class of ultralinear context-free languages. Furthermore, the increase in size when converting arbitrary PDAs accepting ultralinear languages to finite-turn PDAs cannot be bounded by any recursive function. The latter phenomenon is known as non-recursive trade-off. In this paper, we consider finite-turn PDAs that can accept bounded languages. First, we study letter-bounded languages and prove that, in this case, the non-recursive trade-off is reduced to a recursive trade-off, more precisely, to an exponential trade-off. We present a conversion algorithm and show the optimality of the construction by proving tight lower bounds. Furthermore, we study the question of reducing the number of turns of a given finite-turn PDA. Again, we provide a conversion algorithm which shows that, in this case, the trade-off is at most polynomial. Finally, we investigate the more general case of word-bounded languages and show how the results obtained for letter-bounded languages can be extended to word-bounded languages. [Copyright &y& Elsevier]

We investigate the descriptional complexity of little resources added to deterministic one-dimensional real-time iterative arrays. More precisely, we study the impact of adding sublinearly more time obtaining time complexities strictly in between real time and linear time, adding dimensions, allow the communication cell to perform a few nondeterministic steps, and increase the number of bits that may be communicated to neighboring cells slightly. In all cases it is shown that there are arbitrary savings in the size of the descriptions of the arrays which cannot be bounded by any computable function. [ABSTRACT FROM AUTHOR]

Abstract: We study the polynomial state complexity classes 2 and 2, 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 alternations between existential and universal states, starting in an existential or universal state, respectively. This hierarchy is infinite: for , both 2 and 2 are proper subsets of 2 and of 2, since the conversion of a one-way - or -alternating automaton with states into a two-way automaton with a smaller number of alternations requires states. The same exponential blow-up is required for converting a -bounded 2Afa into a -bounded 2Afa and vice versa, that is, 2 and 2 are incomparable. In the case of -bounded 2Afas, the exponential gap applies also for intersection, while in the case of -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.] [Copyright &y& Elsevier]

Abstract: Nondeterministic finite automata (NFA) with at most one accepting computation on every input string are known as unambiguous finite automata (UFA). This paper considers UFAs over a one-letter alphabet, and determines the exact number of states in DFAs needed to represent unary languages recognized by n-state UFAs in terms of a new number-theoretic function . The growth rate of , and therefore of the UFA–DFA tradeoff, is estimated as . The conversion of an n-state unary NFA to a UFA requires UFAs with states, where is the greatest order of a permutation of n elements, known as Landauʼs function. In addition, it is shown that representing the complement of n-state unary UFAs requires UFAs with at least states in the worst case, while the Kleene star requires up to exactly states. [Copyright &y& Elsevier]

With this contribution we would like to commemorate Chandra M. R. Kintala, who passed away in November 2009. We will give short overviews of his CV and his contributions to the field of theoretical and applied computer science and, given the opportunity, will attempt to present his influence on areas like limited nondeterminism and resources as well as software reliability in an exemplary fashion. Finally, we will briefly touch on some research topics which hopefully will be addressed in the not-so-distant future. [ABSTRACT FROM AUTHOR]

Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the number of states needed for transducers used in minimal descriptions of arbitrary strings and, as our main result, show that the state-size hierarchy with respect to a standard encoding is infinite. We consider corresponding hierarchies yielded by more general computable encodings and establish that for a suitably chosen computable encoding every level of the state-size hierarchy can be strict. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity of limited Lindenmayer systems and their deterministic and tabled variants with respect to the number of rules and the number of symbols. In this part, we confine ourselves to propagating limited Lindenmayer systems. We determine the decrease of complexity when the generative capacity is increased. For incomparable families, we give languages that can be described more efficiently in either of these families than in the other. [ABSTRACT FROM AUTHOR]

We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has α states, for all n and α satisfying n ≤ α ≤ 2n. A number α not satisfying this condition is called a magic number (for n). It was shown that no magic numbers exist for general regular languages, whereas trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, star-free languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic. [ABSTRACT FROM AUTHOR]

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata. [ABSTRACT FROM AUTHOR]

We summarize results on the complexity of regular(-like) expressions and tour a fragment of the literature. In particular we focus on the descriptional complexity of the conversion of regular expressions to equivalent finite automata and vice versa, to the computational complexity of problems on regular-like expressions such as, e.g., membership, inequivalence, and non-emptiness of complement, and finally on the operation problem measuring the required size for transforming expressions with additional language operations (built-in or not) into equivalent ordinary regular expressions. [ABSTRACT FROM AUTHOR]

We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages accepted by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case. [ABSTRACT FROM AUTHOR]

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]

The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2m+n-1-2m-1-2n-1+1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2mn for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu ('State complexity of combined operations', Theoret. Comput. Sci., 383 (2007) 140-152). [ABSTRACT FROM AUTHOR]

Abstract: Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. We study the conversion of self-verifying automata to deterministic automata from a descriptional complexity point of view. The main result is the exact cost, in terms of the number of states, of such a simulation. [Copyright &y& Elsevier]

Abstract: Finite automata are probably best known for being equivalent to right-linear context-free grammars and, thus, for capturing the lowest level of the Chomsky-hierarchy, the family of regular languages. Over the last half century, a vast literature documenting the importance of deterministic, nondeterministic, and alternating finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss developments relevant to finite automata related problems like, for example, (i) simulation of and by several types of finite automata, (ii) standard automata problems such as fixed and general membership, emptiness, universality, equivalence, and related problems, and (iii) minimization and approximation. We thus come across descriptional and computational complexity issues of finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved. [Copyright &y& Elsevier]

Abstract: Multi-head finite automata were introduced and first investigated by Rabin and Scott in 1964 and Rosenberg in 1966. Since that time, a vast literature on computational and descriptional complexity issues on multi-head finite automata documenting the importance of these devices has been developed. Although multi-head finite automata are a simple concept, their computational behavior can be already very complex and leads to undecidable or even non-semi-decidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. Additionally the conversions between different types of multi-head finite automata induce in most cases size bounds that cannot be bounded by any recursive function, so-called non-recursive trade-offs. These strong negative results trigger the study of subclasses and alternative characterizations of multi-head finite automata for a better understanding of the nature of non-recursive trade-offs and, thus, the borderline between decidable and undecidable problems. In the present paper, we tour a fragment of this literature. [ABSTRACT FROM AUTHOR]

We introduce PC grammar systems where the components form clusters and the query symbols refer to clusters not individual grammars, i.e., the addressee of the query is not precisely identified. We prove that if the same component replies to all queries issued to a cluster in a rewriting step, then non-returning PC grammar systems with 3 clusters and 7 context-free components are able to generate any recursively enumerable language. We also provide open problems and directions for future research. [ABSTRACT FROM AUTHOR]

A symbol a is called active in an L system G if there is a rule a → υ with a ≠ υ in some table of G. By AcX(L) we denote the number of active symbols necessary to generate L by L systems of type X. For two types X and Y of L systems such that the corresponding languages families $\mathcal{L}(X)$ and $\mathcal{L}(Y)$ satisfy $\mathcal{L}(X)\, \subset \,\mathcal{L}(Y)$, we say that Y is more efficient than X, if there is a sequence of languages $L_n \, \in \,\mathcal{L}(X)$, n ≥ 1, such that AcX(Ln) ≥ n and AcY(Ln) ≤ k for some constant k. In this paper we shall show that the inclusion $\mathcal{L}(X)\, \subset \,\mathcal{L}(Y)$ implies that Y is more efficient than X. Analogous results are presented for some modifications of the measure of active symbols. [ABSTRACT FROM AUTHOR]

This paper provides a first indication that this is true for a system comprised of a static structure described by hyperbolic partial differential equations and is subjected to an external random input force. The system deforms the randomness of an input force sequence in proportion to its algorithmic complexity. The authors demonstrate this by numerical analysis of a one-dimensional vibrating elastic solid (the system) on which we apply a maximally-random force sequence (input). The level of complexity of the system is controlled via external parameters. The output response is the field of displacements observed at several positions on the body. The algorithmic complexity and stochasticity of the resulting output displacement sequence is measured and compared against the complexity of the system. The results show that the higher the system complexity, the more random-deficient the output sequence. [ABSTRACT FROM AUTHOR]

Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals. [ABSTRACT FROM AUTHOR]

It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least 2^{n/2-2} states (the known upper bound is 2^n), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least 2^{sqrt{2n+30}-6} states. A similar state complexity function for scattered superstrings is determined to be exactly 2^{n-2} + 1 for an alphabet of at least n - 2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least 1/5 4sqrt{n/2}n-3/4. [ABSTRACT FROM AUTHOR]

Abstract: A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages. [ABSTRACT FROM AUTHOR]

Abstract: We consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We constructively prove that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages. [Copyright &y& Elsevier]

Abstract: In contrast to the minimization of deterministic finite automata (DFA’s), the task of constructing a minimal nondeterministic finite automaton (NFA) for a given NFA is PSPACE-complete. Moreover, there are no polynomial approximation algorithms with a constant approximation ratio for estimating the number of states of minimal NFA’s. Since one is unable to efficiently estimate the size of a minimal NFA in an efficient way, one should ask at least for developing mathematical proof methods that help to prove good lower bounds on the size of a minimal NFA for a given regular language. Here we consider the robust and most successful lower bound proof technique that is based on communication complexity. In this paper it is proved that even a strong generalization of this method fails for some concrete regular languages. “To fail” is considered here in a very strong sense. There is an exponential gap between the size of a minimal NFA and the achievable lower bound for a specific sequence of regular languages. The generalization of the concept of communication protocols is also strong here. It is shown that cutting the input word into pieces for a size of a minimal nondeterministic finite automaton and investigating the necessary communication transfer between these pieces as parties of a multiparty protocol does not suffice to get good lower bounds on the size of minimal nondeterministic automata. It seems that for some regular languages one cannot really abstract from the automata model that cuts the input words into particular symbols of the alphabet and reads them one by one using its input head. [Copyright &y& Elsevier]

Nondeterministic finite automata (NFAs) were introduced in [68], where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example, (i) simulation of and by several types of finite automata, (ii) minimization and approximation, (iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved. [ABSTRACT FROM AUTHOR]

The simulation of deterministic pushdown automata defined over a one-letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be simulated by a deterministic finite automaton with a number of states that is exponential in s. We prove that this simulation is tight. Furthermore, its cost cannot be reduced even if it is performed by a two-way nondeterministic automaton. We also prove that there are unary languages for which deterministic pushdown automata cannot be exponentially more succinct than finite automata. In order to state this result, we investigate the conversion of deterministic pushdown automata into context-free grammars. We prove that in the unary case the number of variables in the resulting grammar is strictly smaller than the number of variables needed in the case of nonunary alphabets. [ABSTRACT FROM AUTHOR]