173,854 research outputs found
Parikh test sets for commutative languages
No full textA set T ⊆ L is a Parikh test set of L if
c(T) is a test set of c(L).
We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters
DESCRIPTIONAL COMPLEXITY AND PARIKH EQUIVALENCE
No full textThe thesis deals with some topics in the theory of formal languages and automata. Specifically, the thesis deals with the theory of context-free languages and the study of their descriptional complexity.
The descriptional complexity of a formal structure (e.g., grammar, model of automata, etc) is the number of symbols needed to write down its description. While this aspect is extensively treated in regular languages, as evidenced by numerous references, in the case of context-free languages few results are known.
An important result in this area is the Parikh’s theorem. The theorem states that for each context-free language there exists a regular language with the same Parikh image. Given an alphabet Σ = {a1, . . . , am}, the Parikh image is a function ψ : Σ^∗→ N^m that associates with each word w∈Σ^∗, the vector ψ(w)=(|w|_a1, |w|_a2, . . . , |w|_am), where |w|_ai is the number of occurrences of ai in w. The Parikh image of a language L⊆Σ^∗ is the set of Parikh images of its words. For instance, the language {a^nb^n | n ≥ 0} has the same Parikh image as (ab)^∗. Roughly speaking, the theorem shows that if the order of the letters in a word is disregarded, retaining only the number of their occurrences, then context-free languages are indistinguishable from regular languages.
Due to the interesting theoretical property of the Parikh’s theorem, the goal of this thesis is to study some aspects of descriptional complexity according to Parikh equivalence. In particular, we investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view.
We prove that for each one-way nondeterministic automaton with n states there exist Parikh equivalent one-way and two-way deterministic automata with e^O(sqrt(n lnn)) and p(n) states, respectively, where p(n) is a polynomial. Furthermore, these costs are tight. In contrast, if all the words accepted by the given one-way nondeterministic automaton contain at least two different letters, then a Parikh equivalent one-way deterministic automaton with a polynomial number of states can be found.
Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with h variables there exist Parikh equivalent one-way and two-way deterministic automata with 2^O(h^2 ) and 2^O(h) states, respectively. Even these bounds are tight.
A further investigation is the study under Parikh equivalence of the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shuffle, and reversal, we obtain a polynomial state complexity over any fixed alphabet, in contrast to the intrinsic exponential state complexity of some of these operations in the classical version. For projection we prove a superpolynomial state complexity, which is lower than the exponential one of the corresponding classical operation. We also prove that for each two one-way deterministic automata A and B it is possible to obtain a one-way deterministic automaton with a polynomial number of states whose accepted language has as Parikh image the intersection of the Parikh images of the languages accepted by A and B
PARIKH TEST SETS FOR COMMUTATIVE LANGUAGES
No full textAbstract. A set T ⊆ L is a Parikh test set of L iff c(T) is a test set of c(L). We give an effective characterization of Parikh test sets for arbitrary commutative language. 1
Parikh Matrices and Istrail Morphism
No full textA word w is a sequence of symbols. A scattered subword or simply a subword u of the word w is a subsequence of w. Parikh matrix M(w) is an ingenius tool introduced by Mateescu et al (2001) to count certain subwords in a word w. Various properties of Parikh matrices have been established. Two words u and v are said to be M-ambiguous or amiable if their Parikh matrices M(u) and M(v) are the same. On the other hand a morphism f is a mapping on words w whose images f(w) are also words with the property that, f(uv)=f(u)f(v) for given words u and v. Istrail morphism (Istrail, 1977) is a specific kind of morphism on a set {a,b,c} of three symbols. Using this morphism, M-ambiguity or amiability of words based on Parikh matrices is investigated by Atanasiu (2010). Parikh matrices of words that involve certain ratio-property are investigated by Subramanian et al (2009). Here we consider this kind of ratio-property in the context of Istrail morphism and obtain certain properties of morphic images of words under Istrail morphism. Using these properties, conditions are obtained for product of Parikh matrices of such morphic images under Istrail morphism to commute
Two-Way Parikh Automata
No full textParikh automata extend automata with counters whose values can only be tested at the end of the computation, with respect to membership into a semi-linear set. Parikh automata have found several applications, for instance in transducer theory, as they enjoy a decidable emptiness problem.
In this paper, we study two-way Parikh automata. We show that emptiness becomes undecidable in the non-deterministic case. However, it is PSpace-C when the number of visits to any input position is bounded and the semi-linear set is given as an existential Presburger formula. We also give tight complexity bounds for the inclusion, equivalence and universality problems. Finally, we characterise precisely the complexity of those problems when the semi-linear constraint is given by an arbitrary Presburger formula
Counting Problems for Parikh Images
No full textGiven finite-state automata (or context-free grammars) A,B over the same alphabet and a Parikh vector p, we study the complexity of deciding whether the number of words in the language of A with Parikh image p is greater than the number of such words in the language of B. Recently, this problem turned out to be tightly related to the cost problem for weighted Markov chains. We classify the complexity according to whether A and B are deterministic, the size of the alphabet, and the encoding of p (binary or unary)
Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
No full textWe investigate the conversion of nondeterministic finite automata and context-free grammars into Parikh equivalent deterministic finite automata, from a descriptional complexity point of view. We prove that for each nondeterministic automaton with n states there exists a Parikh equivalent deterministic automaton with e O(√n·ln n) states. Furthermore, this cost is tight. In contrast, if all the strings accepted by the given automaton contain at least two different letters, then a Parikh equivalent deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with n variables there exists a Parikh equivalent deterministic automaton with 2 O(n2) states. Even this bound is tight
Efficacy of Ultraviolet Light and Antimicrobials to Reduce Listeria monocytogenes in Chill Brines
No full textChill brines used in ready-to-eat meat processing may be an important source of post-processing contamination by Listeria monocytogenes. The purpose of this study was to determine the efficacy of ultraviolet light (UV) in combination with antimicrobials to reduce L. monocytogenes in fresh and used chill brines. Three different antimicrobials were used in combination with UV; citric acid (CA, 0.2 and 0.5%), dimethyl dicarbonate (DMDC, 250 and 500 ppm), and hydrogen peroxide (HP, 2000 and 4000 ppm).
For fresh brine studies, brine (8.0% w/v NaCl) was prepared and inoculated with a cocktail of three L. monocytogenes strains (approximately 6 log CFU/mL). Brine was treated with UV alone, antimicrobials alone, and combination of UV and antimicrobials. Moreover, to observe the effect of treatment temperature and brine circulation through the UV system on survival of listeriae cells, inoculated brine was circulated through the system without any treatment that served as control for all the treatments. For UV treatment, inoculated brine solution was exposed to UV in an Ultraviolet Water Treatment Unit (Model: AMD 150B/1/2T D; Aquionics Inc., Peak output: 254 nm) fitted with an inline chiller to maintain brine temperature of -1°C. Samples were withdrawn at regular intervals for 120 minutes. When L. monocytogenes population was no longer detectable via direct plating on MOX, enrichment was performed and suspect colonies were confirmed using API-Listeria. For antimicrobial-only (i.e., no UV) treatments, a specific concentration of antimicrobial was added in inoculated brine and samples were taken for 120 minutes. For the brine that received combination of UV and antimicrobial treatments, UV was turned on once a specific concentration of antimicrobial was added in inoculated brine and samples were withdrawn at regular intervals for 120 minutes.
When treated with UV alone, L. monocytogenes population decreased from approximately 6 log CFU/mL to below the detection limit (i.e., 1 log CFU/mL) in 15 minutes with the reduction rate of 0.87 log CFU/mL per minute. However, cells were detectable by enrichment through 120 minutes. The highest rate of decline (0.90 log CFU/mL per minute) was achieved by the combination of UV and 500 ppm DMDC (UV+500 ppm DMDC), which was not significantly different from the reduction rates of UV and UV+0.5% CA. UV+500 ppm DMDC reduced L. monocytogenes to the detection limit in 15 minutes and the organism was not detected by enrichment after 60 minutes. Though the reduction rate of UV+0.5% CA was not significantly lower than the rate of UV+500 ppm DMDC (P>0.05), the former treatment resulted in non-detectable levels more quickly (45 minutes) than the latter (60 minutes). Thus, based on enrichment studies UV+0.5% CA was the most effective treatment in reducing the population of L. monocytogenes in fresh brine. Moreover, when brine was treated with 0.5% CA alone the population decreased to below detection limit in 15 minutes with the rate significantly lower than UV+500 ppm DMDC and UV+0.5% CA (P<0.05). However, L. monocytogenes was not detectable by enrichment from 60 minutes. To summarize, through enrichment studies we observed that UV+0.5% CA, UV+500 DMDC, and 0.5% CA Control were more effective than other treatments in reducing the listeriae population to a non-detectable level.
Spent brine is recycled brine that was obtained from a frankfurter processor after its maximum usage. Results of spent brine studies showed that when brine was treated with UV+4000 ppm HP and UV+2000 ppm HP, L. monocytogenes population decreased to the detection limit in 45 minutes and was not detected by enrichment from 120 minutes. These treatments were observed to be the most effective treatments with a reduction rate of 0.12 log CFU/mL per minute. The reduction rate of some other treatments such as, UV+250 and 500 ppm DMDC, UV+0.2% and 0.5% CA, and UV alone was not significantly different from UV+4000 and 2000 ppm HP. However, the population was detected through enrichment up to 120 minutes in all other treatments.
The results of these studies indicate that combinations of UV and antimicrobial may be more effective than either treatment alone (except 0.5% CA treatment) to process fresh chill brines. However, the antimicrobials and UV were less effective for controlling L. monocytgoenes in spent brine; presumably due to the presence of organic matter.Ph. D
Two-Way Parikh Automata with a Visibly Pushdown Stack (FOSSACS)
No full textIn this paper, we investigate the complexity of the emptiness problem for Parikh automata equipped with a pushdown stack. Pushdown Parikh automata extend pushdown automata with counters which can only be incremented and an acceptance condition given as a semi-linear set, which we represent as an existential Presburger formula over the final values of the counters. We show that the non-emptiness problem both in the deterministic and non-deterministic cases is NP-c. If the input head can move in a two-way fashion, emptiness gets undecidable, even if the pushdown stack is visibly and the automaton deterministic. We define a restriction, called the single-use restriction, to recover decidability in the presence of two-wayness, when the stack is visibly. This syntactic restriction enforces that any transition which increments at least one dimension is triggered only a bounded number of times per input position. Our main contribution is to show that non-emptiness of two-way visibly Parikh automata which are single-use is NExpTime-c. We finally give applications to decision problems for expressive transducer models from nested words to words, including the equivalence problem.SCOPUS: cp.kinfo:eu-repo/semantics/publishe
Parikh's Theorem in Commutative Kleene Algebra
No full textParikh's Theorem says that the commutative image of every context free language is the commutative image of some regular set. Pilling has shown that this theorem is essentially a statement about least solutions of polynomial inequalities. We prove the following general theorem of commutative Kleene algebra, of which Parikh's and Pilling's theorems are special cases: Every system of polynomial inequalities f i (x 1 ; : : : ; xn ) x i , 1 i n, over a commutative Kleene algebra K has a unique least solution in K n ; moreover, the components of the solution are given by polynomials in the coefficients of the f i . We also give a closed-form solution in terms of the Jacobian matrix. 1 Introduction Parikh's theorem [8] says that every context-free language is "letter-equivalent" to a regular set; formally, the commutative image of any context-free language is also the commutative image of some regular set. The commutative image of a string x over the alphabet fa 1 ; : : : ; a k g is ..
- …
