Search

Éditeurs: Mathieu Roche, Nabil Gmati, Amel Ben Abda, Marcellin Nkenlifack, Workflow languages are a key component of the Business Process Management (BPM) discipline: they are used to model business processes in order to facilitate their automatic management by means of BPM systems. There are numerous workflow languages addressing various issues (expressiveness, formal analysis, etc.). In the last decade, some workflow languages based on context-free grammars (having then formal semantics) and offering new perspectives to process modelling, have emerged: LSAWfP (a Language for the Specification of Administrative Workflow Processes) is one of them. LSAWfP has many advantages over other existing languages, but it is its expressiveness (which has been very little addressed in previous works) that is studied in this paper. Indeed, the work in this paper aims to demonstrate that any non-recursive LSAWfP model is a structured workflow. Knowing that the majority of commercial BPM systems only implement structured workflows, the result of this study establishes that, although LSAWfP is still much more theoretical, it is a language with commercial potential., Les langages de workflow occupent une place importante dans la discipline du Business Process Management (BPM) : ils sont utilisés pour modéliser les processus opérationnels afin de faciliter leur gestion automatique à l'aide de systèmes BPM. Il existe de nombreux langages de workflow qui traitent de divers aspects (expressivité, analyse formelle, etc.). Au cours de la dernière décennie, certains langages de workflow basés sur des grammaires algébriques (ayant alors une sémantique formelle) et offrant de nouvelles perspectives à la modélisation des processus ont vu le jour : LSAWfP (a Language for the Specification of Administrative Workflow Processes) est l'un d'entre eux. LSAWfP présente de nombreux avantages par rapport aux langages existants, mais c'est son expressivité (qui a été très peu abordée dans les travaux antérieurs) qui est étudiée dans le présent document. En effet, les travaux présentés dans ce document visent à démontrer que tout modèle LSAWfP non récursif est un workflow structuré. Sachant que la majorité des systèmes BPM commerciaux ne gèrent que des workflows structurés, le résultat de cette étude montre que, bien que LSAWfP soit encore très théorique, il est un langage au potentiel économique certain.

A language over an alphabet $B = A \cup \overline{A}$ of opening ($A$) and closing ($\overline{A}$) brackets, is balanced if it is a subset of the Dyck language $D_B$ over $B$, and it is well-formed if all words are prefixes of words in $D_B$. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TWs of non-linear tree transducers with output alphabet $B^*$ whether or not the output language is balanced., Major changes in Section 3 Balancedness of 2-TWs: instead of proving equivalence of LTWs over the involutive monoid we use the result that equivalence of LTWs over the free group is decidable in polynomial time (arXiv:2001.03480). A short version will be published in the conference proceedings of DLT 2020

We set up the notion of evolutionary P systems as P systems with description of rules, or genomes, and translation, evaluation, selection, and modification operators on genomes. The system has a possibility of evolving a desired function. We propose a tissue evolutionary P system which evolves a context-free grammar generating a given target language, i.e., an evolutionary P system for grammatical inference. Experiments show that the proposed systems can evolve some context-free grammars generating the language \(\{a^nb^n\,|\,n > 0\}\) and the Dyck language over \(\{a,b\}\).

Consider the following one-player game. Take a well-formed sequence of opening and closing brackets (a Dyck word). As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its width: the maximum number of nonempty segments of symbols (separated by blank space) seen during the play.\ud \ud For various initial sequences, we prove upper and lower bounds on the minimum width sufficient for re-pairing. (In particular, the sequence associated with the complete binary tree of height n admits a strategy of width sub-exponential in log n.) Our two key contributions are (1) lower bounds on the width and (2) their application in automata theory: quasi-polynomial lower bounds on the translation from one-counter automata to Parikh-equivalent nondeterministic finite automata. The latter result answers a question by Atig et al. (2016).

Many program-analysis problems can be formulated as graph-reachability problems. Interleaved Dyck language reachability ( InterDyck -reachability) is a fundamental framework to express a wide variety of program-analysis problems over edge-labeled graphs. The InterDyck language represents an intersection of multiple matched-parenthesis languages (i.e., Dyck languages). In practice, program analyses typically leverage one Dyck language to achieve context-sensitivity, and other Dyck languages to model data dependencies, such as field-sensitivity and pointer references/dereferences. In the ideal case, an InterDyck -reachability framework should model multiple Dyck languages simultaneously . Unfortunately, precise InterDyck -reachability is undecidable. Any practical solution must over-approximate the exact answer. In the literature, a lot of work has been proposed to over-approximate the InterDyck -reachability formulation. This article offers a new perspective on improving both the precision and the scalability of InterDyck -reachability: we aim at simplifying the underlying input graph G . Our key insight is based on the observation that if an edge is not contributing to any InterDyck -paths, we can safely eliminate it from G . Our technique is orthogonal to the InterDyck -reachability formulation and can serve as a pre-processing step with any over-approximating approach for InterDyck -reachability. We have applied our graph simplification algorithm to pre-processing the graphs from a recent InterDyck -reachability-based taint analysis for Android. Our evaluation of three popular InterDyck -reachability algorithms yields promising results. In particular, our graph-simplification method improves both the scalability and precision of all three InterDyck -reachability algorithms, sometimes dramatically.

We give a characterization of NPDAs with reversal-bounded counters (NPCMs) in terms of context-free grammars with monotonic counters. We show that the grammar characterization can be used to give simple proofs of previously known results such as the semilinearity of the Parikh map of any language accepted by an NPCM. We prove a Chomsky–Schutzenberger-like theorem: A language L is accepted by an NPCM if and only if there is a k ≥ 1 and an alphabet Σ containing at least k distinguished symbols, p 1 , . . . , p k , such that L = h ( D ∩ E k ( R ) ) for some homomorphism h, Dyck language D ⊆ Σ ⁎ , and regular set R ⊆ Σ ⁎ , where E k ( R ) = { w | w ∈ R , | w | p 1 = ⋯ = | w | p k } . We also give characterizations of other machine models, such as visibly pushdown automata with reversal-bounded counters (VPCMs). We then investigate the complexity of some decision problems concerning these grammatical models. Finally, we introduce other grammatical models equivalent to NPCM.

An experiment is described that confirms the security of a well-studied class of cryptographic protocols (Dolev-Yao intruder model) can be verified by two-way nondeterministic pushdown automata (2NPDA). A nondeterministic pushdown program checks whether the intersection of a regular language (the protocol to verify) and a given Dyck language containing all canceling words is empty. If it is not, an intruder can reveal secret messages sent between trusted users. The verification is guaranteed to terminate in cubic time at most on a 2NPDA-simulator. The interpretive approach used in this experiment simplifies the verification, by separating the nondeterministic pushdown logic and program control, and makes it more predictable. We describe the interpretive approach and the known transformational solutions, and show they share interesting features. Also noteworthy is how abstract results from automata theory can solve practical problems by programming language means., In Proceedings MARS/VPT 2018, arXiv:1803.08668

A Dyck path of length 2 k with e flaws is a path in the integer lattice that starts at the origin and consists of k many ↗ -steps and k many ↘ -steps that change the current coordinate by ( 1 , 1 ) or ( 1 , − 1 ) , respectively, and that has exactly e many ↘ -steps below the line y = 0 . Denoting by D 2 k e the set of Dyck paths of length 2 k with e flaws, the well-known Chung–Feller theorem asserts that the sets D 2 k 0 , D 2 k 1 , … , D 2 k k all have the same cardinality 1 k + 1 2 k k = C k , the k th Catalan number. The standard combinatorial proof of this classical result establishes a bijection f ′ between D 2 k e and D 2 k e + 1 that swaps certain parts of the given Dyck path x , with the effect that x and f ′ ( x ) may differ in many positions. In this paper we strengthen the Chung–Feller theorem by presenting a simple bijection f between D 2 k e and D 2 k e + 1 which has the additional feature that x and f ( x ) differ in only two positions (the least possible number). We also present an algorithm that allows to compute a sequence of applications of f in constant time per generated Dyck path. As an application, we use our minimum-change bijection f to construct cycle-factors in the odd graph O 2 k + 1 and the middle levels graph M 2 k + 1 – two intensively studied families of vertex-transitive graphs – that consist of C k many cycles of the same length.

A language over an alphabet \(\textsf {B}=\textsf {A}\cup \overline{\textsf {A}}\,\) of opening (\(\textsf {A}\)) and closing (\(\overline{\textsf {A}}\,\)) brackets, is balanced if it is a subset of the Dyck language \({\mathbb D}_\textsf {B}\) over \(\textsf {B}\), and it is well-formed if all words are prefixes of words in \({\mathbb D}_\textsf {B}\). We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TW of non-linear tree transducers with output alphabet \(\textsf {B}^*\) whether or not the output language is balanced.

We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$. We call this the $Dyck_{k,n}$ problem. We prove a lower bound of $\Omega(c^k \sqrt{n})$, showing that the complexity of this problem increases exponentially in $k$. Here $n$ is the length of the word. When $k$ is a constant, this is interesting as a representative example of star-free languages for which a surprising $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We give an algorithm with $O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$. Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $\Omega(n^{1.5-\epsilon})$ for the directed 2D grid and $\Omega(n^{2-\epsilon})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions., Comment: arXiv admin note: substantial text overlap with arXiv:1911.12638

Fabric surfaces, made using techniques such as crochet and net-making, are typically worked in a linear order that meanders, without crossing itself, to ultimately visit and build the entire surface. For a closed basket, whose surface is a topological sphere, it is known that the construction can be described by a codeword on a 4-letter alphabet via Mullin&rsquo, s encoding of plane graphs. Mullin&rsquo, s code exemplifies the formal language known as the Shuffled Dyck Language with 2 Types of Parenthesis ( S D L 2 ). Besides its 4-letter alphabet, S D L 2 has some other similarities to DNA: Any word can be &lsquo, evolved&rsquo, via a sequence of local mutations (rewriting rules), and &lsquo, gene-splicing&rsquo, two S D L 2 words, by an insertion or concatenation, produces another S D L 2 word. However, S D L 2 comes up short when we attempt to make a basket with handles. I show that extending the language to S D L 3 , by addition of a third type of parenthesis, succeeds for orientable surfaces with handles&mdash, provided an appropriate choice of cut graph is made.

Дипломна робота: 75 с., 6 табл., 29 рис., 2 дод., 20 джерел. .Темою даної роботи є: «Наочне доведення теореми Хомського- Шютценберже в розширеному формулюванні». Метою даної роботи є доведення теореми Хомського-Шютценберже у розширеному формулюванні. У роботі використано такі елементи теорії фор- мальних мов та автоматів, як скінченні автомати, автомати з магазинною пам’яттю, мова Діка. Було розроблено програмний продукт, що проводить інтерактивне кон- структивне доведення теореми. Він дозволяє перевірити справедливість теоре- ми для будь-якої контекстно-вільної мови. Виконано тестування розробленого програмного продукту. The thesis contains: 75 p., 6 tabl., 29 fig., 2 app., 20 sources. The theme of the thesis is as follows: «A Transparent Proof of the Extended Formulation of the Chomsky-Schutzenberger Representation Theorem». The goal of the thesis is to prove the extended formulation of the Chomsky- Schutzenberger Representation Theorem. The work utilizes such concepts of the formal language and automata theory as finite state machines, pushdown automata, the Dyck language. A software product that executes an interactive proof of the theorem has been developed. It allows to verify that the theorem holds for any given context-free language. Testing of the developed product has been performed.

The generalized Dyck language has been used to analyze the ability of Recurrent Neural Networks (RNNs) to learn context-free grammars (CFGs). Recent studies draw conflicting conclusions on their performance, especially regarding the generalizability of the models with respect to the depth of recursion. In this paper, we revisit several common models and experimental settings, discuss the potential problems of the tasks and analyses. Furthermore, we explore the use of attention mechanisms within the seq2seq framework to learn the Dyck language, which could compensate for the limited encoding ability of RNNs. Our findings reveal that attention mechanisms still cannot truly generalize over the recursion depth, although they perform much better than other models on the closing bracket tagging task. Moreover, this also suggests that this commonly used task is not sufficient to test a model’s understanding of CFGs.

U ovom radu obrađeni su Catalanovi, Motzkinovi i Narayanini brojevi, te Dyckovi putevi. Pokazali smo da su Catalanovi brojevi niz brojeva. Catalanove brojeve smo koristili kao uvod u Dyckove puteve, te Dyckov jezik. Pokazali smo kako je broj Dyckovih puteva duljine n jednak Catalanovom broju Cn. Uveli smo i Naranayine brojeve koji određuju broj Dyckovih puteva duljine n s k vrhova. Zadnji pojam bili su Motzkinovi brojevi koji određuju broj istoimenih puteva. Uz to, napravljen je i računalni program koji računa i iscrtava Motzkinove i Dyckove puteve. This paper is about Catalan, Motzkin and Narayana numbers, as well as Dyck paths. We have shown that Catalan numbers are a sequence. Catalan numbers have been used as an introduction to Dyck paths and the Dyck language. We have shown that the number of Dyck paths for a certain n is equal to the Catalan number Cn, and that the number of Dyck paths for a certain n with k peaks is equal to the Narayana number N(n, k). The last term we introduced was Motzkin numbers, which count the number of paths with the same name. In addition to that, a computer program has been written that counts and draws Motzkin and Dyck paths.

Context-free grammars (CFG) were one of the first formal tools used to model natural languages, and they remain relevant today as the basis of several frameworks. A key ingredient of CFG is the presence of nested recursion. In this paper, we investigate experimentally the capability of several recurrent neural networks (RNNs) to learn nested recursion. More precisely, we measure an upper bound of their capability to do so, by simplifying the task to learning a generalized Dyck language, namely one composed of matching parentheses of various kinds. To do so, we present the RNNs with a set of random strings having a given maximum nesting depth and test its ability to predict the kind of closing parenthesis when facing deeper nested strings. We report mixed results: when generalizing to deeper nesting levels, the accuracy of standard RNNs is significantly higher than random, but still far from perfect. Additionally, we propose some non-standard stack-based models which can approach perfect accuracy, at the cost of robustness.

Trustworthy generation of public random numbers is necessary for the security of a number of cryptographic applications. It was suggested to use the inherent unpredictability of blockchains as a source of public randomness. Entropy from the Bitcoin blockchain in particular has been used in lotteries and has been suggested for a number of other applications ranging from smart contracts to election auditing. In this Arcticle, we analyse this idea and show how an adversary could manipulate these random numbers, even with limited computational power and financial budget.

Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices. In our main result, we derive the Chomsky-Schützenberger Theorem for such quantitative context-free languages, showing that each arises as the image of the intersection of a Dyck language and a recognizable language under a suitable morphism. Moreover, we show that quantitative context-free languages are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings. We also investigate under which conditions quantitative context-free languages assume only finitely many values.

The problem of enumerating and denumerating words generated by Dyck grammars arises in the work of compilers for high-level programming languages and a number of other applications. The present paper proposes an algorithm for the fast enumeration and denumeration of words of Dyck languages; the complexity of this algorithm per one symbol of enumerated words is O(log3n log log n) bit operations, provided that the Schonhage-Strassen multiplication and division algorithmis used. The well-knownmethods applied earlier possess complexityO(n) per one symbol of enumerated words. The construction of the proposed algorithm is based on the Ryabko method.

Weir [34] proved a Chomsky-Schutzenberger-like representation theorem for the string languages of tree-adjoining grammars, where the Dyck language Dn in the Chomsky-Schutzenberger characterization is replaced by the intersection D2n ∩ g(D2n), where g is a certain bijection on the alphabet consisting of 2n pairs of brackets. This paper presents a generalization of this theorem to the string languages that are the yield images of the tree languages generated by simple (i.e., linear and non-deleting) context-free tree grammars. This result is obtained through a natural generalization of the original Chomsky-Schutzenberger theorem to the tree languages of simple context-free tree grammars. We use Rogers’s [24,23] notion of multi-dimensional trees to state this latter theorem in a very general, abstract form.

International audience; We introduce the notion of pattern in the context of lattice paths, and investigate it in the specific case of Dyck paths. Similarly to the case of permutations, the pattern-containment relation defines a poset structure on the set of all Dyck paths, which we call the Dyck pattern poset . Given a Dyck path PP, we determine a formula for the number of Dyck paths covered by PP, as well as for the number of Dyck paths covering PP. We then address some typical pattern-avoidance issues, enumerating some classes of pattern-avoiding Dyck paths. We also compute the generating function of Dyck paths avoiding any single pattern in a recursive fashion, from which we deduce the exact enumeration of such a class of paths. Finally, we describe the asymptotic behavior of the sequence counting Dyck paths avoiding a generic pattern, we prove that the Dyck pattern poset is a well-ordering and we propose a list of open problems.

The famous theorem by Chomsky and Schutzenberger (CST) says that every context-free language L over an alphabet Σ is representable as h ( D ∩ R ) , where D is a Dyck language over a set Ω of brackets, R is a local language and h is an alphabetic homomorphism that erases unboundedly many symbols. Berstel found that the number of erasures can be linearly limited if the grammar is in Greibach normal form; Berstel and Boasson (and later, independently, Okhotin) proved a non-erasing variant of CST for grammars in Double Greibach Normal Form. In all these CST statements, however, the size of the Dyck alphabet Ω depends on the grammar size for L. In the Stanley variant of the CST, | Ω | only depends on | Σ | and not on the grammar, but the homomorphism erases many more symbols than in the other versions of CST; also, the regular language R is strictly locally testable but not local. We prove a new version of CST which combines both features of being non-erasing and of using a grammar-independent alphabet. In our construction, | Ω | is polynomial in | Σ | , namely O ( | Σ | 46 ) , and the regular language R is strictly locally testable. Using a recent generalization of Medvedev's homomorphic characterization of regular languages, we prove that the degree in the polynomial dependence of | Ω | on | Σ | may be reduced to just 2 in the case of linear grammars in Double Greibach Normal Form.

It is shown how to endow a hierarchy of sets of binary patterns with the structure of an abstract,normed C*-algebra. In the course we also recover an intermediate connection with the words of a Dyck language and Tempereley-Lieb algebras for which we also find that an effective arithmetic code is possible albeit of greater complexity. We also discuss possible applications associated with signal theory and waveform engineering on possible ways to embed discrete computational structures in an analog continuum substrate., 17 p., 6 figures

The context-free language (CFL) reachability problem is a well-known fundamental formulation in program analysis. In practice, many program analyses, especially pointer analyses, adopt a restricted version of CFL-reachability, Dyck-CFL-reachability, and compute on edge-labeled bidirected graphs. Solving the all-pairs Dyck-CFL-reachability on such bidirected graphs is expensive. For a bidirected graph with n nodes and m edges, the traditional dynamic programming style algorithm exhibits a subcubic time complexity for the Dyck language with k kinds of parentheses. When the underlying graphs are restricted to bidirected trees, an algorithm with O(n log n log k) time complexity was proposed recently. This paper studies the Dyck-CFL-reachability problems on bidirected trees and graphs. In particular, it presents two fast algorithms with O(n) and O(n + m log m) time complexities on trees and graphs respectively. We have implemented and evaluated our algorithms on a state-of-the-art alias analysis for Java. Results on standard benchmarks show that our algorithms achieve orders of magnitude speedup and consume less memory.

We consider the problem of fixing sequences of unbalanced parentheses. A classic algorithm based on dynamic programming computes the optimum sequence of edits required to solve the problem in cubic time. We show the first algorithm that runs in linear time when the number of necessary edits is small. More precisely, our algorithm runs in O(n) + dO(1) time, where n is the length of the sequence to be fixed and d is the minimum number of edits. The problem of fixing parentheses sequences is related to the task of repairing semi-structured documents such as XML and JSON.

We study the problem of testing whether a context-free language is included in a fixed set L0, where L0 is the language of words reducing to the empty word in the monoid defined by a complete string rewrite system. We prove that, if the monoid is cancellative, then our inclusion problem is polynomially reducible to the problem of testing equivalence of straight-line programs in the same monoid. As an application, we obtain a polynomial time algorithm for testing if a context-free language is included in a Dyck language (the best previous algorithm for this problem was doubly exponential).

In this paper, we obtain some refinement of representation theorems for context-free languages by using Dyck languages, insertion systems, strictly locally testable languages, and morphisms. For instance, we improved the Chomsky-Schutzenberger representation theorem and show that each context-free language L can be represented in the form L = h (D ∩ R), where D is a Dyck language, R is a strictly 3-testable language, and h is a morphism. A similar representation for context-free languages can be obtained, using insertion systems of weight (3, 0) and strictly 4-testable languages.

The statistics concerning the number of appearances of a string τ in Dyck paths as well as its appearances in odd and even level have been studied extensively by several authors using mostly algebraic methods. In this work a different, bijective approach is followed giving some known as well as some new results.

The theorem by Chomsky and Schutzenberger (CST) says that every context-free language L over alphabet \(\varSigma \) is representable as \(h(D_k \cap R)\) where \(D_k\) is the Dyck language over k pairs of brackets, R is a local (i.e., 2-strictly-locally-testable language) regular language, and h is an alphabetic homomorphism that may erase symbols; the Dyck alphabet size depends on the size of the grammar generating L. In the Stanley variant, the Dyck alphabet size only depends on the size of \(\varSigma \), but the homomorphism has to erase many more symbols than in the previous version. Berstel found that the number of erasures in CST can be linearly limited if the grammar is in Greibach normal form, and recently Okhotin proved a non-erasing variant of CST for grammars in Double Greibach normal form. In both statements the Dyck alphabet depends on the grammar size. We present a new non-erasing variant of CST that uses a Dyck alphabet independent from the grammar size and a regular language that is strictly-locally-testable, similarly to a recent generalization of Medvedev theorem for regular languages.

The CFG recognition problem is: given a context-free grammar $\mathcal{G}$ and a string $w$ of length $n$, decide if $w$ can be obtained from $\mathcal{G}$. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in $O(n^{\omega})$ time, where $\omega

We consider a generalization of the Dyck language. We have a set of opening and a set of closing brackets and a relation that gives the pairs of brackets that can be used in the generalized Dyck language. This Dyck language is a handy coding for several classes of labeled trees.We present an algorithm that generates all words of length 2n of the generalized Dyck language lexicographically. Thereby, each word is computed from its predecessor according to the lexicographical order without any knowledge about the words generated before. Additionally, we introduce a condition on the relation for the generalized Dyck language to be simply generated, which means that an algorithm needs to read only the suffix to be changed in order to compute the successor of a word according to the lexicographical order. We present an algorithm that checks whether a Dyck language is simply generated or not.For an arbitrary relation, we compute the sth moments of the random variable describing the length of the suffix to be cha...

We continue the investigation of properties defined by formal languages. This study was initiated by Alon et al. [1], who described an algorithm for testing properties defined by regular languages. Alon et al. also considered several context free languages, and in particular Dyck languages, which contain strings of properly balanced parentheses. They showed that the first Dyck language, which contains strings over a single type of pairs of parentheses, is testable in time independent of n, where n is the length of the input string. However, the second Dyck language, defined over two types of parentheses, requires Ω (log n) queries. Here we describe a sublinear-time algorithm for testing all Dyck languages. Specifically, the running time of our algorithm is O(n2/3/e3), where e is the given distance parameter. Furthermore, we improve the lower bound for testing Dyck languages to Ω (n1/11) for constant e. We also describe a testing algorithm for the context free language LREV = {uurvvr : u, v ∈ Σ*}, where Σ is a fixed alphabet. The running time of our algorithm is O(√n/e), which almost matches the lower bound given by Alon et al. [1].