Search

FC is a finite model variant on the theory of concatenation, FC [ REG ] extends FC with regular constraints. This paper considers the languages generated by their conjunctive query fragments, FC-CQ and FC[REG]-CQ. We compare the expressive power of FC [ REG ] - CQ to that of various related language generators, such as regular expressions, patterns, and typed patterns. We then consider decision problems for FC - CQ and FC [ REG ] - CQ , and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines FC - CQ based on the logic FC , it can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations. [ABSTRACT FROM AUTHOR]

We investigate the descriptional complexity of the νi- and αi-products with 0 ≤ i ≤ 2 of two automata, for reset, permutation, permutation-reset, and finite automata in general. This is a continuation of the recent studies on the state complexity of the well-known cascade product undertaken in [7, 8]. Here we show that in almost all cases, except for the direct product (ν0) and the cascade product (α0) for certain types of automata operands, the whole range of state complexities, namely the interval [1,nm], where n is the state complexity of the left operand and m that of the right one, is attainable. To this end we prove a simulation result on products of automata that allows us to reduce the products of automata in question to the ν0, α0, and a double sided α0-product. [ABSTRACT FROM AUTHOR]

Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as 1-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case, the size gap from 1-limited automata to one-way deterministic finite automata is double exponential.Here we introduce two restricted versions of 1-limited automata, once-marking1-limited automata and always-marking1-limited automata, and study their descriptional complexity. We prove that once-marking 1-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic 1-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking 1-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic.We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation. [ABSTRACT FROM AUTHOR]

While the closure of a language family ℒ under certain language operations is the least family of languages which contains all members of ℒ and is closed under all of the operations, a kernel of ℒ is a maximal family of languages which is a sub-family of ℒ and is closed under all of the operations. Here we investigate properties of kernels of general language families and operations defined thereon as well as kernels of (deterministic) (linear) context-free languages with a focus on Boolean operations. While the closures of language families are unique, this uniqueness is not obvious for kernels. We consider properties of language families and of operations that yield unique and non-unique, i.e. a set, of kernels. For the latter case, the question whether the union of all kernels coincides with the language family, or whether there are languages that do not belong to any kernel is addressed. Additionally, languages that are mandatory for each (Boolean) kernel and languages that are optional for (Boolean) kernels are studied. That is, we consider the intersection of all Boolean kernels as well as their union. The expressive capacities of these families are addressed leading to a hierarchical structure. Further closure properties are considered. Furthermore, we study descriptional complexity aspects of these families, where languages are represented by context-free grammars with proofs attached. It turns out that the size trade-offs between all families in question and deterministic context-free languages are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the latter system to the former. [ABSTRACT FROM AUTHOR]

We design Latvian quantum finite state automata (LQFAs) recognizing unary regular languages with isolated cut point 1 2. From an architectural viewpoint, we suitably combine two LQFAs recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part any given unary regular language L consists of. In particular, both these LQFAs incorporate a sub-module discriminating strings on the basis of their length.Both the number of basis states and the isolation around the cut point of the resulting LQFAs for L exponentially depend on the size of the minimal deterministic finite state automaton for L. Moreover, the recognition of L tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows. [ABSTRACT FROM AUTHOR]

The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limited automata, the sizes of the resulting devices are polynomial in the sizes of the simulated machines. The situation is different when the operations are applied to deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. The costs for product and star do not reduce if the given machines are sweeping two-way deterministic finite automata. These bounds are tight. [ABSTRACT FROM AUTHOR]

We investigate the state complexity of languages resulting from the cascade product of two minimal deterministic finite automata with  n and  m states, respectively. More precisely we study the magic number problem of the cascade product operation and show what range of complexities can be produced in case the left automaton is unary, that is, has only a singleton letter alphabet. Here we distinguish the cases when the involved automata are reset automata, permutation automata, permutation-reset automata, or do not have any restriction on their structure. It turns out that the picture on the obtained state complexities of the cascade product is diverse, and for all cases, except where the left automaton is a unary permutation(-reset) or a deterministic finite automaton without structural restrictions, and the right one is a reset automaton or a deterministic finite automaton without structural restrictions, we are able to identify state sizes that cannot be reached — these numbers are called "magic." [ABSTRACT FROM AUTHOR]

It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of m2k−O(1), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least n ⋅ (m − 1) 2 k − O (log k) nonterminal symbols. [ABSTRACT FROM AUTHOR]

We investigate the accepting state complexity of deterministic finite automata for regular languages obtained by applying one of the following operations on languages accepted by permutation automata: union, quotient, complement, difference, intersection, Kleene star, Kleene plus, and reversal. The paper thus joins the study of the accepting state complexity of regularity preserving language operations which was initiated in [J. Dassow, J. Autom., Lang. Comb.21 (2016) 55–67]. We show that for almost all of the above-mentioned operations, except for reversal and quotient, there is no difference in the accepting state complexity for permutation automata compared to deterministic finite automata in general. For both reversal and quotient we prove that certain accepting state complexities cannot be obtained; these numbers are called "magic" in the literature. Moreover, we solve the left open accepting state complexity problem for the intersection of unary languages accepted by permutation automata and deterministic finite automata in general. [ABSTRACT FROM AUTHOR]

We study properties of a two-dimensional grammar introduced recently for use in document analysis and recognition. The grammar is obtained from the two-dimensional context-free grammar by limiting the form of productions. Variants (ranks) of the grammar with regard to productions complexity are defined. If the grammar is restricted to produce one-row pictures only, it generates regular languages. We suggest that the lowest-rank variant can be considered as a natural generalization of the regular matrix grammar, which in addition shares some of its good properties. Namely, it can be parsed in time linear in the input area and the emptiness problem is still decidable for the grammar. However, we also show that the higher-rank variants do not loosen complexity of the context-free grammar too much. There is a conditional lower bound preventing to propose a linear-time parsing algorithm. Moreover, the grammar is able to simulate the 2-counter Minsky machine, which results in non-recursive trade-offs between grammars of different ranks and also in undecidability of the emptiness problem. [ABSTRACT FROM AUTHOR]

An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep takes place on the input string, while any subsequent sweep works on the output of the previous one. We consider devices with one-way motion and two-way motion, that is, sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we first study devices that perform a constant number of sweeps, which are known to characterize exactly the regular languages. We determine the descriptional costs of removing two-way motion, nondeterminism, and sweeps, and, in particular, the costs for the conversion to deterministic or nondeterministic finite automata. Moreover, the special case of unary languages is investigated, and a language family is presented that is immune to two-way motion and almost immune to nondeterminism, in the sense that these resources do not help in reducing the number of states and/or sweeps. Finally, we look at devices that perform a non-constant number of sweeps. Here, it turns out that in the deterministic case two-way motion is more powerful than one-way motion, whereas nondeterminism and one-way motion can be more powerful than determinism and two-way motion. [ABSTRACT FROM AUTHOR]

We prove lower bounds on the length of regular expressions for finite languages by methods from arithmetic circuit complexity. First, we show a reduction: the length of a regular expression for a language L ⊆ { 0 , 1 } n is bounded from below by the minimum size of a monotone arithmetic formula computing a polynomial that has L as its set of exponent vectors. This result yields lower bounds for the language of all words with exactly k ones and n − k zeros and for the language of all Dyck words of length 2 n. Second, we adapt a lower bound method for multilinear arithmetic formulas by so-called log-product polynomials to regular expressions. With this method we show almost tight lower bounds for the language of all n -bit binary numbers that are divisible by a given odd integer p and for the language of all permutations of { 1 , ... , n }. [ABSTRACT FROM AUTHOR]

Unary self-verifying symmetric difference automata have a known tight bound of 2 n − 1 − 1 for their state complexity. We now consider the non-unary case and show that, for every n ≥ 2 , there is a regular language ℒ n accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with n states, such that its equivalent minimal deterministic finite automaton has 2 n − 1 states. Furthermore, given any SV-XNFA with n states, it is possible, up to isomorphism, to find at most another | G L (n , ℤ 2) | − 1 equivalent SV-XNFA. Finally, we show that for a certain set of non-unary SV-XNFA, 2 n − 1 is a tight bound on the state complexity. [ABSTRACT FROM AUTHOR]

Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k , are considered. These devices and their accepted languages are called k -reversible automata and k -reversible languages, respectively. The existence of k -reversible languages which are not (k − 1) -reversible is known, for each k > 1. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are k -reversible for some k. Conditions characterizing the class of k -reversible languages, for each fixed k , and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not k -reversible, but which accepts a k -reversible language, into an equivalent k -reversible finite automaton, is presented. [ABSTRACT FROM AUTHOR]

An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are "one-way" devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace (lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic. [ABSTRACT FROM AUTHOR]

An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are "one-way" devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace (lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic. [ABSTRACT FROM AUTHOR]

1-limited automata are single-tape Turing machines with strong rewriting restrictions, that do not allow them to recognize more than regular languages. However, 1-limited automata can be significantly more succinct than equivalent finite automata: in fact, the size gap from 1-limited automata to one-way deterministic finite automata is double exponential. In this paper we present and discuss some languages which can be used as witnesses of the gaps between different kinds of 1-limited automata and finite automata. Among them, refining previous techniques, we show that a language proposed long time ago by Meyer and Fischer as a witness of the optimality of the subset construction for finite state automata, can also be used as witness of all the currently known size gaps between 1-limited automata and different variants of finite automata. We also discuss some open problems and possible further lines of investigation. [ABSTRACT FROM AUTHOR]

A matrix insertion-deletion system (or matrix ins-del system) is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model very simplistic fragments of sequential programs based on insertion and deletion as elementary operations as can be found in biocomputing. We are investigating such systems with limited resources as formalized in descriptional complexity. A traditional descriptional complexity measure of such a matrix ins-del system is its size s = (k ; n , i ′ , i ′ ′ ; m , j ′ , j ′ ′) , where the parameters from left to right represent the maximal matrix length, maximal insertion string length, maximal length of left contexts in insertion rules, maximal length of right contexts in insertion rules; the last three are deletion counterparts of the previous three parameters. We call the sum n + i ′ + i ′ ′ + m + j ′ + j ′ ′ the sum-norm of s. We show that matrix ins-del systems of sum-norm 4 and sizes (3; 1, 0, 0; 1, 2, 0), (3; 1, 0, 0; 1, 0, 2), (2; 1, 2, 0; 1, 0, 0), (2; 1, 0, 2; 1, 0, 0), and (2; 1, 1, 1; 1, 0, 0) describe the recursively enumerable languages. Moreover, matrix ins-del systems of sizes (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0) can describe at least the regular closure of the linear languages. In fact, we show that if a matrix ins-del system of size s can describe the class of linear languages LIN , then without any additional resources, matrix ins-del systems of size s also describe the regular closure of LIN . Finally, we prove that matrix ins-del systems of sizes (2; 1, 1, 0; 1, 1, 0) and (2; 1, 0, 1; 1, 0, 1) can describe at least the regular languages. [ABSTRACT FROM AUTHOR]

In this paper we consider the model of single insertion-deletion systems that at each step insert or delete a single symbol in a context-free manner (i.e. at any position in the word). The corresponding operation is performed if the word contains a set of permitting (that have to be present in the word) and/or forbidding (that must not be present in the word) strings of some size. The main result of this paper states that if forbidding strings of size 2 and permitting strings of size 1 are used then computational completeness can be achieved; moreover, checking for a single permitting symbol is sufficient. We also show that in the case of systems having rules with forbidding conditions only, all regular languages can be obtained. Finally, we show the computational non-completeness in the case of systems using rules with forbidding strings of size 1 (single symbols) and permitting strings of any finite size. [ABSTRACT FROM AUTHOR]

Stateless ordered restart-delete automata (stl-ORD-automata) are studied. These are obtained from the stateless ordered restarting automata (stl-ORWW-automata) by introducing an additional restart-delete operation, which, based on the surrounding context, deletes a single letter. While the stl-ORWW-automata accept the regular languages, we show that the swift stl-ORD-automata yield a characterization for the class of context-free languages. Here a stl-ORD-automaton is called swift if it can move its window to any position after performing a restart. We also study the descriptional complexity of swift stl-ORD-automata and relate them to limited context restarting automata. [ABSTRACT FROM AUTHOR]

Splicing systems are generative mechanisms introduced by Tom Head in 1987 to model the biological process of DNA recombination. The computational engine of a splicing system is the "splicing operation", a cut-and-paste binary string operation defined by a set of "splicing rules", quadruples r = (u 1 , u 2 ; u 3 , u 4) where u 1 , u 2 , u 3 , u 4 are words over an alphabet Σ. For two strings x 1 u 1 u 2 y 1 and x 2 u 3 u 4 y 2 , applying the splicing rule r produces the string x 1 u 1 u 4 y 2 . In this paper we focus on a particular type of splicing systems, called (i , j) semi-simple splicing systems, i = 1 , 2 and j = 3 , 4 , wherein all splicing rules r have the property that the two strings in positions i and j in r are singleton letters, while the other two strings are empty. The language generated by such a system consists of the set of words that are obtained starting from an initial set called "axiom set", by iteratively applying the splicing rules to strings in the axiom set as well as to intermediately produced strings. We consider semi-simple splicing systems where the axiom set is a regular language, and investigate the descriptional complexity of such systems in terms of the size of the minimal deterministic finite automata that recognize the languages they generate. [ABSTRACT FROM AUTHOR]

Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. In traditional regulated rewriting, the most interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on forbidding sets, i.e., a matrix is applicable to a sentential form w only if none of the words in its forbidding set occurs as a subword in w. This gives rise to further natural descriptional complexity measures: How long could words in forbidding sets be? How many words could be in any forbidding set? How many matrices contain non-empty forbidding contexts? As context-free grammars with forbidding sets are known as generalized forbidding grammars, we call this variant of matrix grammars also generalized forbidding. In this paper, we attempt to answer the four questions above while studying the computational completeness of generalized forbidding matrix grammars. In the course of our studies, we also define several new normal forms for type-0 grammars that might be of independent interest. • Combining conditional matrix (KM) and generalized forbidding (GF) grammars, we define generalized forbidding matrix grammars. • We tackle the question how small measures of descriptional complexity could be while maintaining computational completeness. • Our studies also add new results to the theory of KM and of GF grammars. • We introduce a new normal form for type-0 grammars that was useful for us and that might be also of independent interest. [ABSTRACT FROM AUTHOR]

The model of deterministic input-driven multi-counter automata is introduced and studied. On such devices, the input letters uniquely determine the operations on the underlying data structure that is consisting of multiple counters. We study the computational power of the resulting language families and compare them with known language families inside the Chomsky hierarchy. In addition, it is possible to prove a proper counter hierarchy depending on the alphabet size. This means that any input alphabet induces an upper bound which depends on the alphabet size only, such that k + 1 counters are more powerful than k counters as long as k is less than this bound. The hierarchy interestingly collapses at the level of the bound. Furthermore, we investigate the closure properties of the language families. For input-driven multi-counter automata with 0 or 1 counter, we discuss the computational complexity of their decidable problems. For k ≥ 2 counters, the decidability problems of emptiness, finiteness, universality, inclusion, equivalence, regularity, and context-freeness are shown to be non-semidecidable. Finally, we study descriptional complexity aspects of input-driven multi-counter automata. It is shown that a nondeterministic device can be determinized and that 2 n − 1 is a necessary and sufficient blow-up in the number of states for the determinization. For the operational state complexity of deterministic input-driven multi-counter automata under Boolean operations, tight bounds on the number of states are established. Finally, it turns out that the size trade-offs between deterministic input-driven multi-counter automata with k + 1 and k counters are non-recursive, that is, they are not bounded by any recursive function. [ABSTRACT FROM AUTHOR]

We partially answer an open question on small computational devices: how many neurons are needed by a spiking neural P system with communication on request (SNQ P Systems) to achieve universality? We provide an answer in the case when the SNQ P System uses at least 5 types of spikes. Our work shows that 6 neurons are enough to achieve universality as number generators, number accepters and function computation device. We achieve this result by using only two neuron to simulate the instructions labels and one type of spike to emulate a register. [ABSTRACT FROM AUTHOR]

Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s. [ABSTRACT FROM AUTHOR]

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated. [ABSTRACT FROM AUTHOR]

In this paper, we continue the research on accepting networks of evolutionary processors where the filters belong to several special families of regular languages. We consider families of codes or ideals and subregular families which are defined by restricting the resources needed for generating or accepting them (the number of states of the minimal deterministic finite automaton accepting a language of the family as well as the number of non-terminal symbols or the number of production rules of a right-linear grammar generating such a language). We insert the newly defined language families into the hierachy of language families obtained by using as filters languages of other subregular families (such as ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, combinational, finite, monoidal, nilpotent, or commutative languages). [ABSTRACT FROM AUTHOR]

Input-driven pushdown automata (IDPDA) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the input symbol. Nowadays such devices are usually defined such that popping from the empty pushdown does not block the computation but continues it with empty pushdown. Here, we consider IDPDAs that have a more balanced behavior concerning pushing and popping. Digging input-driven pushdown automata (DIDPDA) are basically IDPDAs that, when forced to pop from the empty pushdown, dig a hole of the shape of the popped symbol in the bottom of the pushdown. Popping further symbols from a pushdown having a hole at the bottom deepens the current hole furthermore. The hole can only be filled up by pushing symbols previously popped. We study the impact of the new behavior of DIDPDAs on their power and compare their capacities with the capacities of ordinary IDPDAs and tinput-driven pushdown automata which are basically IDPDAs whose input may be preprocessed by length-preserving finite state transducers. It turns out that the capabilities are incomparable. We address the determinization of DIDPDAs and their descriptional complexity, closure properties, and decidability questions. [ABSTRACT FROM AUTHOR]

Iterative arrays with restricted internal inter-cell communication are investigated. A quantitative measure for the communication is defined by counting the number of uses of the links between cells and it is differentiated between the sum of all communications of an accepting computation and the maximum number of communications per cell occurring in accepting computations. The computational complexity of both classes of devices is investigated and put into relation. In addition, a strict hierarchy depending on the maximum number of communications per cell is established. Furthermore, it is shown that almost all commonly studied decidability questions are not semidecidable for iterative arrays with restricted communication. Finally, non-recursive trade-offs are proved among the iterative arrays providing the strict hierarchy depending on the maximum number of communications per cell. [ABSTRACT FROM AUTHOR]

We examine the accepting state complexity, i.e., the minimal number of accepting states of deterministic finite automata for languages resulting from unary and binary operations on languages with accepting state complexity given as a parameter. This is a continuation of the work of [J. Dassow: On the number of accepting states of finite automata, J. Autom., Lang. Comb., 21, 2016]. We solve most of the open problems mentioned thereof. In particular, we consider the operations of intersection, symmetric difference, right and left quotients, reversal, and permutation (on finite languages), where we obtain precise ranges of accepting state complexities. We also consider symmetric difference on unary finite languages where we obtain a non-contiguous range of accepting state complexities. [ABSTRACT FROM AUTHOR]

Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding grammars to deterministic finite automata is known. The same size gap is also known from constant-height pushdown automata and 1 -limited automata to deterministic finite automata. Constant-height pushdown automata and 1 -limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Furthermore, a polynomial size simulation by 1 -limited automata is presented. However, the converse transformation is proved to cost exponential. Finally, a different simulation shows that also the conversion of deterministic constant-height pushdown automata into deterministic 1 -limited automata costs polynomial. [ABSTRACT FROM AUTHOR]

In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic (inductive or constructive) definition of (primitive) recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer [ABSTRACT FROM AUTHOR]