328,004 research outputs found
Operational state complexity under Parikh equivalence
No full textWe investigate, under Parikh equivalence, 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 deterministic automata A and B it is possible to obtain a 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. Finally, we prove that for each finite set there exists a small context-free grammar defining a language with the same Parikh image
Kirit S. Parikh (éd.), India Development Report 1999-2000
No full textKennedy Loraine. Kirit S. Parikh (éd.), India Development Report 1999-2000. In: Tiers-Monde, tome 42, n°165, 2001. La libéralisation économique en Inde : inflexion ou rupture ? sous la direction de Frédéric Landy. pp. 225-226
Operational State Complexity under Parikh Equivalence (Extended Abstract)
No full textWe investigate, under Parikh equivalence, the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shue, and reversal, we obtain a polynomial state complexity over any xed 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 deterministic automata A and B it is possible to obtain a 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'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 ..
Kirit S. Parikh (éd.), India Development Report 1999-2000
No full textKennedy Loraine. Kirit S. Parikh (éd.), India Development Report 1999-2000. In: Tiers-Monde, tome 42, n°165, 2001. La libéralisation économique en Inde : inflexion ou rupture ? sous la direction de Frédéric Landy. pp. 225-226
History-deterministic Parikh Automata
No full textParikh automata extend finite automata by counters that can be tested for
membership in a semilinear set, but only at the end of a run. Thereby, they
preserve many of the desirable properties of finite automata. Deterministic
Parikh automata are strictly weaker than nondeterministic ones, but enjoy
better closure and algorithmic properties. This state of affairs motivates the
study of intermediate forms of nondeterminism. Here, we investigate
history-deterministic Parikh automata, i.e., automata whose nondeterminism can
be resolved on the fly. This restricted form of nondeterminism is well-suited
for applications which classically call for determinism, e.g., solving games
and composition. We show that history-deterministic Parikh automata are
strictly more expressive than deterministic ones, incomparable to unambiguous
ones, and enjoy almost all of the closure properties of deterministic automata.Comment: arXiv admin note: text overlap with arXiv:2207.0769
A Fully Equational Proof of Parikh's Theorem
No full textWe show that the validity of Parikh's theorem for context-free languages depends only on a few equational properties of least pre-fixed points. Moreover, we exhibit an infinite basis of µ-term equations of continuous commutative idempotent semirings
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
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
No full textWe 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 states there exist Parikh equivalent one-way and two-way deterministic automata with and states, respectively, where is a polynomial. Furthermore, these costs are tight.
In contrast, if all the words accepted by the given 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 and states, respectively.
Even these bounds are tight
- …
