Search

• The topological entropy function is surjective. • Languages of deterministic epsilon-free k-counter automata have 0 entropy. • Languages of deterministic epsilon-free k-stack automata have bounded entropy. We introduce the notions of topological entropy of a formal language and of a topological automaton. We show that the entropy function is surjective and bound the entropy of languages accepted by deterministic ε -free push-down automata with an arbitrary amount of stacks. [ABSTRACT FROM AUTHOR]

Formal languages and automata (FLA) theory is perceived by many as one of the hardest topics to teach or learn at the undergraduate level, due to the abstract nature of its contents; often containing proofs, lots of symbolic notations, and specifications of abstract computing machines that are difficult for many students to relate with. One way of approaching this problem is to administer numerous practice problems to students to aid learning. In this paper, we present: definitions of formal rules (using context-free grammar notations) for the synthesis of practice problems and solutions in a sub-domain of formal language theory – regular expressions, new algorithms for implementing these rules with iterations of generated problem instances and associated solutions. Generated problems are then embedded in predefined, short text response and multiple-choice question templates. The implementation of this technique produced numerous problems and solutions that can be used as practice, test or examination questions to support the teaching of regular expressions as a topic in FLA at the undergraduate level. [ABSTRACT FROM AUTHOR]

The core entities of computer science include formal languages, specifications, models, programs, implementations, semantic theories, type inference systems, abstract and physical machines. While there are conceptual questions concerning their nature, and in particular ontological ones (Turner 2018), our main focus here will be on the relationships between them. These relationships have an extensional aspect that articulates the propositional connection between the two entities, and an intentional one that fixes the direction of governance. An analysis of these two aspects will drive our investigation; an investigation that will touch upon some of the central concerns of the philosophy of computer science (Turner 2017). [ABSTRACT FROM AUTHOR]

Probabilistic &mega;-automata are variants of nondeterministic automata over infinite words where all choices are resolved by probabilistic distributions. Acceptance of a run for an infinite input word can be defined using traditional acceptance criteria for &mega;-automata, such as Büchi, Rabin or Streett conditions. The accepted language of a probabilistic &mega;-automata is then defined by imposing a constraint on the probability measure of the accepting runs. In this paper, we study a series of fundamental properties of probabilistic &mega;-automata with three different language-semantics: (1) the probable semantics that requires positive acceptance probability, (2) the almost-sure semantics that requires acceptance with probability 1, and (3) the threshold semantics that relies on an additional parameter λ ϵ]0, 1[ that specifies a lower probability bound for the acceptance probability. We provide a comparison of probabilistic &mega;-automata under these three semantics and nondeterministic &mega;-automata concerning expressiveness and efficiency. Furthermore, we address closure properties under the Boolean operators union, intersection and complementation and algorithmic aspects, such as checking emptiness or language containment. Categories and Subject Descriptors: D.2.4 [Software Engineering]: Software/Program Verification -- Model checking; F 1.1 [Computation by Abstract Devices]: Models of Computations -- Automata (e.g., finite, pushdown, resource-bounded); F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs; F.4.3 [Mathematical Logics and Formal Languages]: Formal Languages; G.3 [Probability and Statistics]: Markov Processes General Terms: Languages, Verification, Theory [ABSTRACT FROM AUTHOR]

The quotient of a formal language K by another language L is the set of all strings obtained by taking a string from K that ends with a suffix of a string from L , and removing that suffix. The quotient of a regular language by any language is always regular, whereas the context-free languages and many of their subfamilies, such as the linear and the deterministic languages, are not closed under the quotient operation. This paper establishes the closure of the family of languages recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the quotient operation. A construction of automata representing the result of the operation is given, and its state complexity with respect to nondeterministic IDPDA is shown to be exactly m 2 n , where m and n are the numbers of states in the automata recognizing K and L , respectively. [ABSTRACT FROM AUTHOR]

Edit distance ℓ -neighbourhood of a formal language is the set of all strings that can be transformed to one of the strings in this language by at most ℓ insertions and deletions. Both the regular and the context-free languages are known to be closed under this operation, whereas the family recognized by deterministic pushdown automata is not. This paper establishes the closure of the family recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the edit distance neighbourhood operation. For an n -state nondeterministic IDPDA with n stack symbols, an automaton for its edit distance ℓ -neighbourhood using O (n ℓ + 1) states is constructed, and an asymptotically matching lower bound is established. For an n -state deterministic IDPDA, its 1-neighbourhood in the worst case requires a deterministic IDPDA with at least 2 Ω (n 2) states. [ABSTRACT FROM AUTHOR]

The theoretical background to automata and formal languages represents a complex learning area for students. Computer tools for interacting with the algorithm and interfaces to visualize its different steps can assist the learning process and make it more attractive. In this paper, we present a web application for learning some of the most common algorithms in an appealing way. They are specifically linked to the recognition of regular languages that are, taught in classes on both automata theory and compiler design. Although several simulators are available to students, they usually only serve to validate grammars, automata, and languages, rather than helping students to learn the internal processes that an algorithm can perform. The resource presented here can execute and display each algorithm process, step by step, providing explanations on each step that assist student comprehension. Additionally, as a web‐based resource, it can be used on any device with no need for specific software installation. [ABSTRACT FROM AUTHOR]

Presents information on a study which focuses on testing graph properties and its connection to learning and approximation. Methodology of the study; Results and discussion.

Presents information on a study which investigated an approximation algorithm for set cover. Methodology of the study; Results and discussion.

Abstract: Formal Languages and Automata (FLA) address mathematical models able to specify and recognize languages, their properties and characteristics. Although solid knowledge of FLA is extremely important for a B.Sc. degree in Computer Science and similar fields, the algorithms and techniques covered in the course are complex and difficult to assimilate. Therefore, this article presents FLApp, a mobile application—which we consider the new way to reach students—for teaching FLA. The application—developed for mobile phones and tablets running Android—provides students not only with answers to problems involving Regular, Context‐free, Context‐Sensitive, and Recursively Enumerable Languages, but also an Educational environment that describes and illustrates each step of the algorithms to support students in the learning process. [ABSTRACT FROM AUTHOR]

İn this paper, we introduce the concepts of order-congruences and strong order-congruences on an ordered semihypergroup S, and obtain the relationship between strong order-congruences and pseudoorders on S. Furthermore, we characterize the (strong) order-congruences by the p-chains, where p is a (strong) congruence on S. Moreover, we give a method of constructing order-congruences, and prove that every hyperideal I of an ordered semihypergroup S is congruence class of one order-congruence on S if and only if I is convex. Finally, we define and study the strong order-congruence generated by a strong congruence. As an application of the results of this paper, we solve an open problem on ordered semihypergroups given by Davvaz et al. [ABSTRACT FROM AUTHOR]

We introduce and study the model of diving queue automata which are basically finite automata equipped with a storage medium that is organized as a queue. Additionally, two queue heads are provided at both ends of the queue that can move in a read-only mode inside the queue. In particular, we consider suitable time constraints and the case where only a finite number of turns on the queue is allowed. As one main result we obtain a proper queue head hierarchy, that is, two heads are better than one head, and one head is better than no head. Moreover, it is shown that the model with one queue head, finitely many turns, and no time constraints as well as the model with two queue heads, possibly infinitely many turns, and time constraints is captured by P and has a P-complete membership problem. We obtain also that a subclass of the model with two queue heads is already captured by logarithmic space. Finally, we consider decidability questions and it turns out that almost nothing is decidable for the model with two queue heads, whereas we obtain that at least emptiness and finiteness are decidable for subclasses of the model with one queue head. [ABSTRACT FROM AUTHOR]

We study the differences of Martin-Löf random left-c.e. reals and show that for each pair of such reals α , β there exists a unique number r > 0 such that q α − β is a Martin-Löf random left-c.e. real for each positive rational q > r and a Martin-Löf random right-c.e. real for each positive rational q < r . Based on this result we develop a theory of differences of halting probabilities, which answers a number of questions about Martin-Löf random left-c.e. reals, including one of the few remaining open problems from the list of open questions in algorithmic randomness [21] . The halting probability of a prefix-free machine M restricted to a set X is the probability that the machine halts and outputs an element of X . Becher, Figueira, Grigorieff, and Miller asked whether Ω U ( X ) is Martin-Löf random when U is universal and X is a Π 1 0 set. We apply our theory of differences of halting probabilities to give a positive answer. [ABSTRACT FROM AUTHOR]

We show that the information rate of the language accepted by a reversal-bounded deterministic counter machine is computable. For the nondeterministic case, we provide computable upper bounds. For the class of languages accepted by multi-tape deterministic finite automata, the information rate is computable as well. [ABSTRACT FROM AUTHOR]

A multi-head 1-way pushdown automaton with k heads is a pushdown automaton with k 1-way read heads on the input tape and a stack. It was previously shown that the deter- ministic variant of the model cannot accept all the context free languages. In this paper, we introduce a 2-tape, 2-head model namely Watson-Crick pushdown automata where the content of the second tape is determined using a complementarity relation, similar to Watson-Crick automata. We show computational powers of nondeterministic two-head pushdown automata and nondeterministic Watson-Crick pushdown automata are same. Moreover, deterministic Watson-Crick pushdown automata can accept all the context free languages. [ABSTRACT FROM AUTHOR]

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w , the tape contents is reduced to a particular word within a finite number of applications of these contextual rewritings. Here we extend the limited context restarting automata by using additional global means to structure the reductions they execute. In fact, we study regulated lc-R-automata, for which a regular control language is used to restrict the set of admissible reduction sequences, and we propose random context conditions to restrict the place at which a transition of an lc-R-automaton can be applied. [ABSTRACT FROM AUTHOR]

We prove completeness for some language-theoretic models of the full Lambek calculus and its various fragments. First we consider syntactic concepts and syntactic concepts over regular languages, which provide a complete semantics for the full Lambek calculus $${\mathbf {FL}}_\perp $$ . We present a new semantics we call automata-theoretic, which combines languages and relations via closure operators which are based on automaton transitions. We establish the completeness of this semantics for the full Lambek calculus via an isomorphism theorem for the syntactic concepts lattice of a language and a construction for the universal automaton recognizing the same language. Finally, we use automata-theoretic semantics to prove completeness of relation models of binary relations and finite relation models for the Lambek calculus without and with empty antecedents (henceforth: $$\mathbf L $$ and $$\mathbf L1 $$ ), thus solving a problem left open by Pentus (Ann Pure Appl Log 75:179-213, 1995). [ABSTRACT FROM AUTHOR]

We shall consider nondeterministic and deterministic automata equipped with a limited pushdown (constant height npda s and dpda s) as well as their two-way versions (constant height 2 npda s and 2 dpda s). We show two double-exponential gaps for these devices, namely, (i) for complementing constant height one-way npda s and (ii) for converting constant height 2 npda s or 2 dpda s into one-way devices. [ABSTRACT FROM AUTHOR]

Regular tree languages are a popular device for reachability analysis over term rewrite systems, with many applications like analysis of cryptographic protocols, or confluence and termination analysis. At the heart of this approach lies tree automata completion, first introduced by Genet for left-linear rewrite systems. Korp and Middeldorp introduced so-called quasi-deterministic automata to extend the technique to non-left-linear systems. In this paper, we introduce the simpler notion of state-compatible automata, which are slightly more general than quasi-deterministic, compatible automata. This notion also allows us to decide whether a regular tree language is closed under rewriting, a problem which was not known to be decidable before. The improved precision has a positive impact in applications which are based on reachability analysis, namely termination and confluence analysis. Our results have been formalized in the theorem prover Isabelle/HOL. This allows to certify automatically generated proofs that are using tree automata techniques. [ABSTRACT FROM AUTHOR]

It is shown that every automaton acceptable for rectangular labyrinths can be reduced to an automaton that behaves according to either the left-hand rule or the right-hand rule, or does not move at all, in every plane rectangular labyrinth without leaves. This enables us to approach certain fundamental problems of the theory of automata in labyrinths in a quite different way. [ABSTRACT FROM AUTHOR]

Visibly Pushdown Automata ( VPA ) are a special case of pushdown machines where the stack operations are driven by the input. In this paper, we consider VPA with multiple stacks , namely n-VPA , with n > 1 . These automata introduce a useful model to effectively describe concurrent pushdown systems using a simple communication mechanism between stacks. We show that n -VPA are strictly more expressive than VPA. Indeed, n -VPA accept some context-sensitive languages that are not context-free and some context-free languages that are not accepted by any VPA. Nevertheless, we show that the class of languages accepted by n -VPA is closed under union and intersection. On the contrary, this class turns out to be neither closed under complementation nor determinizable. Moreover, we show that the emptiness problem for n -VPA is undecidable. By adding an ordering constraint on stacks ( n -OVPA), decidability of emptiness can be recovered, as well as the closure under complementation. Using these properties along with the automata-theoretic approach, one can prove that the model checking problem over n -OVPA models against n -OVPA specifications is decidable. [ABSTRACT FROM AUTHOR]

In this paper, we introduce some basic measures for insertion-deletion system and matrix insertion-deletion system. These measures are based on the number of variables, the number of productions and the number of symbols in a grammar. We show that with respect to these measures, both the systems are more succinct over context-free grammars in representing certain families of context-free languages. [ABSTRACT FROM AUTHOR]

It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is and the nondeterministic state complexity of insertion is precisely , where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning. [ABSTRACT FROM AUTHOR]

We investigate subfamilies of context-free languages that share two important properties. The languages are accepted by input-driven pushdown automata as well as by a reversible pushdown automata. So, the languages are input driven and reversible at the same time. This intersection can be defined on the underlying language families or on the underlying machine classes. It turns out that the latter class is properly included in the former. The relationships between the language families obtained in this way and to reversible context-free languages as well as to input-driven languages are studied. In general, a hierarchical inclusion structure within the real-time deterministic context-free languages is obtained. Finally, the closure properties of these families under the standard operations are investigated and it turns out that all language families introduced are anti-AFLs. [ABSTRACT FROM AUTHOR]

This paper provides efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: • The classes of the Boolean hierarchy over level Σ 1 of the dot-depth hierarchy are decidable in NL (previously only the decidability was known). The same remains true if predicates mod d for fixed d are allowed. • If modular predicates for arbitrary d are allowed, then the classes of the Boolean hierarchy over level Σ 1 are decidable. • For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level Σ 2 of the Straubing–Thérien hierarchy are decidable in NL. This is the first decidability result for this hierarchy. • The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for NL. • The membership problems for quasi-aperiodic languages and for d -quasi-aperiodic languages are logspace many-one complete for PSPACE. [ABSTRACT FROM AUTHOR]

Deterministic finite automata equipped with the storage medium of a queue are investigated towards their ability to perform reversible computations, that is, computations in which every occurring configuration has exactly one successor and exactly one predecessor. A first result is that any queue automaton can be simulated by a reversible one. So, reversible queue automata are as powerful as Turing machines. Therefore it is of natural interest to impose time restrictions to queue automata. Here we consider quasi realtime and realtime computations. It is shown that every reversible quasi realtime queue automaton can be sped up to realtime. On the other hand, under realtime conditions reversible queue automata are less powerful than general queue automata. Furthermore, we exhibit a lower bound of ... time steps for realtime queue automata witness languages to be accepted by any equivalent reversible queue automaton. We study the closure properties of reversible realtime queue automata and obtain similar results as for reversible deterministic pushdown automata. Finally, we investigate decidability questions and obtain that all commonly studied questions such as emptiness, finiteness, or equivalence are not semidecidable for reversible realtime queue automata. Furthermore, it is not semidecidable whether an arbitrary given realtime queue automaton is reversible. [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. When d > 2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa. [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 consider the computational complexity of problems related to partial word automata. Roughly speaking, a partial word is a word in which some positions are unspecified and a partial word automaton is a finite automaton that accepts a partial word language--here the unspecified positions in the word are represented by a "hole" symbol . A partial word language L0 can be transformed into an ordinary language L by using a -substitution. In particular, we investigate the complexity of the compression or minimization problem for partial word automata, which is known to be NP-hard. We improve on the previously known complexity on this problem, by showing PSPACE-completeness. In fact, it turns out that almost all problems related to partial word automata, such as, e.g., equivalence and universality, are already PSPACE- complete. Moreover, we also study these problems under the further restriction that the involved automata accept only finite languages. In this case, the complexities of the studied problems drop from PSPACE-completeness down to coNP-hardness and containment in P2 depending on the problem investigated. [ABSTRACT FROM AUTHOR]

Studies on biological processes in nature are of great interest to researchers as it involves modelling and understanding processes using different perspectives. The proposed model emphasises on Formal Languages and Automata Theory. A generative device and a recognition device are designed to monitor biological processes. It is shown that the proposed models are capable of recognising the biological processes by using glycolysis in pancreatic β cells and glycogen metabolism in astrocytes. The acceptance or rejection state of recognising device monitors the completion of the defined processes. Generative device produces strings that represent set of enzymes significant for initiating the biological process. Such generative and recognising devices assist in designing of biocomputing machines at molecular level. [ABSTRACT FROM AUTHOR]

A (factor-)reference in a word is a special symbol that refers to another factor in the same word; a reference is dereferenced by substituting it with the referenced factor. We introduce and investigate the class ref-REG of all languages that can be obtained by taking a regular language R and then dereferencing all possible references in the words of R . We show that ref-REG coincides with the class of languages defined by regular expressions as they exist in modern programming languages like Perl, Python, Java, etc. (often called REGEX languages). [ABSTRACT FROM AUTHOR]