Search

Researches about semantic computing are usually evaluated by experiments, lacking support from the theory of computation. But traditional finite automata are defined on a fixed finite set of states. They will be invalid when a different application needs to change the states. However, semantic computing always asks for more robust automata that can modify itself according to the changes of states. Therefore, in this paper, we redefine traditional automata in more robust forms by semantic computing. The intuitive idea is when the state which an automaton is supposed to enter has changed, we drive automata into a state that is similar to the original one. We can find another similar state in the original state set to replace the changed state by semantic similarity. Based on the theories of semantic similarity, there always exists a similar state. Therefore, once a state has changed, we can always find a similar state to replace it, which means that we can empower automata to adapt to the changes of states. Our new automata bridge the gap between semantic computing and the theory of computation. Furthermore, we also redefine fuzzy finite automata and pushdown automata in more robust forms. Finally, we provide an application about the weather forecast, which indicates how to overcome the limitations of traditional automata. [ABSTRACT FROM AUTHOR]

Finite automata transform periodic sequences into periodic ones. The period of the output sequence is bounded from above by a linear function of input period. It is known that pushdown automata also preserve the set of periodic sequences. We prove that the output period for one-counter pushdown automata is bounded from above by a quadratic function of input period. We also give an example of an automaton with a quadratic lower bound on output period. [ABSTRACT FROM AUTHOR]

Consider the full modular group PSL(ℤ) with presentation 〈 U, S| U , S 〉. Motivated by our investigations on quasi-modular forms and the Minkowski question mark function (so that this paper may be considered as a necessary appendix), we are led to the following natural question. Some words in the alphabet { U, S} are equal to the unity; for example, USU SU is such a word of length 8, and USU SUSU S U is such a word of length 15. We consider the following integer sequence. For each n ∈ ℕ, let t( n) be the number of words in the alphabet { U, S} that equal the identity in the group. This is the new entry A265434 into the Online Encyclopedia of Integer Sequences. We investigate the generating function of this sequence and prove that it is an algebraic function over ℚ( x) of degree 3. As an interesting generalization, we formulate the problem of describing all algebraic functions with a Fermat property. [ABSTRACT FROM AUTHOR]

We generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and decidability of emptiness for VPDA languages) carry over to the generalized models, but other results (e.g., determinization and closure under complementation) do not carry over, in general. We define a model that combines the desirable features of a VPDA and reversal-bounded counters, called 2-phase VPCM, and show that the deterministic and nondeterministic versions are equivalent and that the family of languages they define is closed under Boolean operations and has decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. We also investigate the finite-ambiguity and finite-valuedness problems concerning these devices. [ABSTRACT FROM AUTHOR]

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results. [ABSTRACT FROM AUTHOR]

Yamakami (Theoret. Comput. Sci., 2011) studies non-uniform context-free languages. Here, the length of advice is assumed to be the same as that of an input. Let CFL and CFL/n denote the class of all context-free languages and its nonuniform version, respectively. We let CFL(2) denote the class of intersections of two context-free languages. An interesting direction of a research is asking how complex CFL(2) is, relative to CFL. Yamakami raised a problem whether there is a CFL-immune set in CFL(2) - CFL/n. The best known so far is that LSPACE - CFL/n has a CFL-immune set, where LSPACE denotes the class of languages recognized in logarithmic-space. We present an affirmative solution to his problem. Two key concepts of our proof are the overlapped palindrome and Yamakami's swapping lemma. The swapping lemma is applicable to the setting where the pumping lemma (Bar-Hillel's lemma) does not work. Our proof is an example showing how useful the swapping lemma is. In addition, by means of Kolmogorov complexity, we show the following: With respect to realtime deterministic context-free languages, the non-uniform class with parallel advice is not a subset of that with serial advice. [ABSTRACT FROM AUTHOR]

Yamakami (Theoret. Comput. Sci., 2011) studies non-uniform context-free languages. Here, the length of advice is assumed to be the same as that of an input. Let CFL and CFL/n denote the class of all context-free languages and its nonuniform version, respectively. We let CFL(2) denote the class of intersections of two context-free languages. An interesting direction of a research is asking how complex CFL(2) is, relative to CFL. Yamakami raised a problem whether there is a CFL-immune set in CFL(2) - CFL/n. The best known so far is that LSPACE - CFL/n has a CFL-immune set, where LSPACE denotes the class of languages recognized in logarithmic-space. We present an affirmative solution to his problem. Two key concepts of our proof are the overlapped palindrome and Yamakami's swapping lemma. The swapping lemma is applicable to the setting where the pumping lemma (Bar-Hillel's lemma) does not work. Our proof is an example showing how useful the swapping lemma is. In addition, by means of Kolmogorov complexity, we show the following: With respect to realtime deterministic context-free languages, the non-uniform class with parallel advice is not a subset of that with serial advice. [ABSTRACT FROM AUTHOR]

Pseudorandomness has played a central role in modern cryptography, finding theoretical and practical applications to various fields of computer science. A function that generates pseudorandom strings from shorter but truly random seeds is known as a pseudorandom generator. Our generators are designed to fool languages (or equivalently, Boolean-valued functions). In particular, our generator fools advised context-free languages, namely, context-free languages assisted by external information known as advice, and moreover our generator is made almost one-to-one, stretching n -bit seeds to n + 1 bits. We explicitly construct such a pseudorandom generator, which is computed by a deterministic Turing machine using logarithmic space and also belongs to CFLMV(2)/ n —a functional extension of the 2-conjunctive closure of CFL with the help of appropriate deterministic advice. In contrast, we show that there is no almost one-to-one pseudorandom generator against context-free languages if we demand that it should be computed by a nondeterministic pushdown automaton equipped with a write-only output tape. Our generator naturally extends known pseudorandom generators against advised regular languages. Our proof of the CFL/ n -pseudorandomness of the generator is quite elementary and, in particular, one part of the proof utilizes a special feature of the behaviors of nondeterministic pushdown automata, called a swapping property, which is interesting in its own right, generalizing the swapping lemma for context-free languages. [ABSTRACT FROM AUTHOR]

We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted by deterministic multipass automata is exactly the Boolean closure of the class of deterministic context-free languages while the class of languages accepted by nondeterministic multipass automata is exactly the class of poly-context-free languages, that is, languages which are the intersection of finitely many context-free languages. We illustrate the use of these automata by studying groups whose word problems are in the above classes. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new dynamical system of a pushdown automaton, called automaton with a stack (AS). We prove that every AS has a periodic configuration by construction of it. Next, we define a special case of an AS, called AS with finite memory and we prove that the AS has a finite memory if and only if it is positively expansive. Furthermore, we prove that every AS with finite memory has shadowing property. Having these two properties, we set a finite-to-one map between an AS with finite memory and some vertex subshift, which gives us a semi-conjugacy between these two systems. Additionally, we define an algorithm to decide if a given graphGdescribes some AS with finite memory and to calculate maximal depth of a stack. [ABSTRACT FROM AUTHOR]

Abstract: A pushdown automata based algorithm for searching all occurrences of a tree pattern in a rooted directed labelled ordered subject tree is presented. The algorithm allows tree pattern matching with don’t care symbols and with multiple patterns. The subject tree may be for example an abstract syntax tree of a compiler or validating source text editor. Further, a construction and practical evaluation of a simulation algorithm of pushdown automata based tree pattern matching is described. [Copyright &y& Elsevier]

A new approach to the 2D pattern matching and specifically to 2D text indexing is proposed. A transformation of a 2D text into the form of a tree is presented. It preserves the context of each element of the 2D text. The tree can be linearised using the prefix notation into the form of a string (a linear text) and the pattern matching is performed in this text. Pushdown automata indexing the 2D text are constructed over the tree representation. They allow to search for 2D prefixes, 2D suffixes, and 2D factors of the 2D text in time proportional to the size of the representation of a 2D pattern. This result achieves the properties analogous to the results obtained in tree pattern matching and string indexing. [ABSTRACT FROM AUTHOR]

We introduce and investigate blackhole pushdown automata, variants of pushdown automata, where a string can always be pushed to the pushdown, but only a given depth of the pushdown content is remembered (the rest of the pushdown content is either canceled or becomes inaccessible). We also study blackhole variants of regulated pushdown automata, where the automaton in some distinguished states checks the form of its pushdown content against a given control language. We present characterizations of several language families in terms of these constructs. [ABSTRACT FROM AUTHOR]

context-free grammar corresponds to a system of equations in languages. The language generated by the grammar is the smallest solution of the system. We give a necessary and sufficient condition for an arbitrary solution to be the smallest one. We revive an old criterion to decide that a grammar has a unique solution. All this fits in an approach to search for a grammar for an arbitrary language that is given by other means. The approach is illustrated by the derivation of a grammar for a certain set of bit strings. The approach is used to give an elegant derivation of the grammar for a language accepted by a pushdown automaton. [ABSTRACT FROM AUTHOR]

Pushdown automata may contain transitions that are never used in any accepting run of the automaton. We present an algorithm for detecting such useless transitions. A finite automaton that captures the possible stack content during runs of the pushdown automaton, is first constructed in a forward procedure to determine which transitions are reachable, and then employed in a backward procedure to determine which of these transitions can lead to a final state. An implementation of the algorithm is shown to exhibit a favorable performance. [ABSTRACT FROM AUTHOR]

A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let \hbox{NPDA-TURN}(\,f(n)) and \hbox{DPDA-TURN}(\,f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f  ( n ) turns for any input of length n . In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: \hbox{DPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log f(n)\log n) , and \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf NSPACE} (\log f(n)\log n) . In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: \hbox{DPDA-TURN}(O(1))\subseteq {\bf DL} and \hbox{NPDA-TURN}(O(1))\subseteq {\bf NL} , from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL , and the other is that a more tight inclusion \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log n) cannot be derived unless {\bf DL}={\bf NL} , though \hbox{NPDA-TURN} (\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log^2n) holds. [ABSTRACT FROM AUTHOR]

In this paper we consider two properties of a pushdown dynamical system (PDS) — its topological entropy and reversibility. First, we present a formula to calculate the topological entropy of an arbitrary PDS based on classical approach to the topological entropy of Bowen and Dinaburg. Next, we calculate the topological entropy for some exemplary systems. As a second goal we provide three necessary conditions for reversibility. We mainly focus on a class of reversible pushdown dynamical systems called PDS with internal state storage (PDSIS). [ABSTRACT FROM AUTHOR]