Relevant bibliographies by topics / Pumping lemma

Academic literature on the topic 'Pumping lemma'

Author: Grafiati
Published: 10 December 2022
Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Pumping lemma.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Pumping lemma"

1

Lu, Ruqian, and Hong Zheng. "Pumping Lemma for Quantum Automata." International Journal of Theoretical Physics 43, no. 5 (May 2004): 1191–217. http://dx.doi.org/10.1023/b:ijtp.0000048609.66662.87.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kászonyi, L. "A pumping lemma for DLI-languages." Discrete Mathematics 258, no. 1-3 (December 2002): 105–22. http://dx.doi.org/10.1016/s0012-365x(02)00265-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kostolányi, Peter. "A pumping lemma for flip-pushdown languages." RAIRO - Theoretical Informatics and Applications 50, no. 4 (June 2, 2016): 295–311. http://dx.doi.org/10.1051/ita/2016003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Colton, Don. "A restated pumping lemma for context-free languages." ACM SIGACT News 24, no. 2 (April 1993): 87. http://dx.doi.org/10.1145/156063.156066.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ewert, Sigrid, and Andries van der Walt. "A pumping lemma for random permitting context languages." Theoretical Computer Science 270, no. 1-2 (January 2002): 959–67. http://dx.doi.org/10.1016/s0304-3975(01)00171-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Yu, Sheng. "A pumping lemma for deterministic context-free languages." Information Processing Letters 31, no. 1 (April 1989): 47–51. http://dx.doi.org/10.1016/0020-0190(89)90108-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Gazdag, Zsolt, Krisztián Tichler, and Erzsébet Csuhaj-Varjú. "A Pumping Lemma for Permitting Semi-Conditional Languages." International Journal of Foundations of Computer Science 30, no. 01 (January 2019): 73–92. http://dx.doi.org/10.1142/s0129054119400045.

Full text
Abstract:
Permitting semi-conditional grammars (pSCGs) are extensions of context-free grammars where each rule is associated with a word [Formula: see text] and such a rule can be applied to a sentential form [Formula: see text] only if [Formula: see text] is a subword of [Formula: see text]. We consider permitting generalized SCGs (pgSCGs) where each rule [Formula: see text] is associated with a set of words [Formula: see text] and [Formula: see text] is applicable only if every word in [Formula: see text] occurs in [Formula: see text]. We investigate the generative power of pgSCGs with no erasing rules and prove a pumping lemma for their languages. Using this lemma we show that pgSCGs are strictly weaker than context-sensitive grammars. This solves a long-lasting open problem concerning the generative power of pSCGs. Moreover, we give a comparison of the generating power of pgSCGs and that of forbidding random context grammars with no erasing rules.
APA, Harvard, Vancouver, ISO, and other styles
8

Fried, Michael N., and Mayer Goldberg. "A Pumping Lemma for Invalid Reductions of Fractions." College Mathematics Journal 41, no. 5 (November 2010): 357–64. http://dx.doi.org/10.4169/074683410x521955.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

MALETTI, ANDREAS. "RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA." International Journal of Foundations of Computer Science 16, no. 04 (August 2005): 723–41. http://dx.doi.org/10.1142/s012905410500325x.

Full text
Abstract:
Bottom-up tree series transducers (tst) over the semiring [Formula: see text] are implemented with the help of bottom-up weighted tree automata (wta) over an extension of [Formula: see text]. Therefore bottom-up [Formula: see text]-weighted tree automata ([Formula: see text]-wta) with [Formula: see text] a distributive Ω-algebra are introduced. A [Formula: see text]-wta is essentially a wta but uses as transition weight an operation symbol of the Ω-algebra [Formula: see text] instead of a semiring element. The given tst is implemented with the help of a [Formula: see text]-wta, essentially showing that [Formula: see text]-wta are a joint generalization of tst (using IO-substitution) and wta. Then a semiring and a wta are constructed such that the wta computes a formal representation of the semantics of the [Formula: see text]-wta. The applicability of the obtained presentation result is demonstrated by deriving a pumping lemma for deterministic finite [Formula: see text]-wta from a known pumping lemma for deterministic finite wta. Finally, it is observed that the known decidability results for emptiness cannot be applied to obtain decidability of emptiness for finite [Formula: see text]-wta. Thus with help of a weaker version of the derived pumping lemma, decidability of the emptiness problem for finite [Formula: see text]-wta is shown under mild conditions on [Formula: see text].
APA, Harvard, Vancouver, ISO, and other styles
10

Ghorani, Maryam, Sunita Garhwal, and Somaye Moghari. "Lattice-valued tree pushdown automata: Pumping lemma and closure properties." International Journal of Approximate Reasoning 142 (March 2022): 301–23. http://dx.doi.org/10.1016/j.ijar.2021.12.002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Pumping lemma"

1

Cogliati, Joshua Joseph. "Visualizing the pumping lemma for regular languages." Thesis, Montana State University, 2004. http://etd.lib.montana.edu/etd/2004/cogliati/CogliatiJ0805.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Barthwal, Aditi. "A formalisation of the theory of context-free languages in higher order logic." Phd thesis, 2010. http://hdl.handle.net/1885/16399.

Full text
Abstract:
We present a formalisation of the theory of context-free languages using the HOL4 theorem prover. The formalisation of this theory is not only interesting in its own right, but also gives insight into the kind of manipulations required to port a pen-and-paper proof to a theorem prover. The mechanisation proves to be an ideal case study of how intuitive textbook proofs can blow up in size and complexity, and how details from the textbook can change during formalisation. The mechanised theory provides the groundwork for our subsequent results about SLR parser generation. The theorems, even though well-established in the field, are interesting for the way they have to be “reproven” in a theorem prover. Proofs must be recast to be concrete enough for the prover: patching deductive gaps which are relatively easily grasped in a text proof, but beyond the automatic capabilities of contemporary tools. The library of proofs, techniques and notations developed here provides a basis from which further work on verified language theory can proceed at a quickened pace. We have mechanised classical results involving context-free grammars and pushdown automata. These include but are not limited to the equivalence between those two formalisms, the normalisation of CFGs, and the pumping lemma for proving a language is not context-free. As an application of this theory, we describe the verification of SLR parsing. Among the various properties proven about the parser we show, in particular, soundness: if the parser results in a parse tree on a given input, then the parse tree is valid with respect to the grammar, and the leaves of the parse tree match the input; and completeness: if the input belongs in the language of the grammar then the parser constructs the correct parse tree for the input with respect to the grammar. In addition, we develop a version of the algorithm that is executable by automatic translation from HOL to SML. This alternative version of the algorithm requires some interesting termination proofs. We conclude with a discussion of the issues we faced while mechanising pen-and-paper proofs. Carefully written formal proofs are regarded as rigorous for the audience they target. But when such proofs are implemented in a theorem prover, the level of detail required increases dramatically. We provide a discussion and a broad categorisation of the causes that give rise to this.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Pumping lemma"

1

Kozen, Dexter C. "Using the Pumping Lemma." In Automata and Computability, 72–76. New York, NY: Springer New York, 1997. http://dx.doi.org/10.1007/978-1-4612-1844-9_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kozen, Dexter C. "The Pumping Lemma for CFLs." In Automata and Computability, 148–56. New York, NY: Springer New York, 1997. http://dx.doi.org/10.1007/978-1-4612-1844-9_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Sorokin, Alexey. "Pumping Lemma and Ogden Lemma for Displacement Context-Free Grammars." In Developments in Language Theory, 154–65. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-09698-8_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kwee, Kent, and Friedrich Otto. "A Pumping Lemma for Ordered Restarting Automata." In Descriptional Complexity of Formal Systems, 226–37. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-60252-3_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Smith, Tim. "A Pumping Lemma for Two-Way Finite Transducers." In Mathematical Foundations of Computer Science 2014, 523–34. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44522-8_44.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Kalociński, Dariusz. "On Computability and Learnability of the Pumping Lemma Function." In Language and Automata Theory and Applications, 433–40. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-04921-2_35.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Kuske, Sabine. "A maximum path length pumping lemma for edge-replacement languages." In Fundamentals of Computation Theory, 342–51. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-57163-9_29.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Kanazawa, Makoto. "The Pumping Lemma for Well-Nested Multiple Context-Free Languages." In Developments in Language Theory, 312–25. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02737-6_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kühnemann, Armin. "A pumping lemma for output languages of macro tree transducers." In Trees in Algebra and Programming — CAAP '96, 44–58. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-61064-2_28.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Gasperoni, Franco, Uwe Schwiegeishohn, and John Turek. "Optimal loop scheduling on multiprocessors: A pumping lemma for p-processor schedules." In Lecture Notes in Computer Science, 51–56. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-60222-4_96.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Pumping lemma"

1

CUI, LICONG, and GUO-QIANG ZHANG. "A GENERALIZED NON-PUMPING LEMMA FOR REGULAR LANGUAGES." In Proceedings of the QL&SC 2012. WORLD SCIENTIFIC, 2012. http://dx.doi.org/10.1142/9789814401531_0057.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Guo, Xiuhong, and Jiehong Xu. "Pumping lemma in lattice finite automata: A note." In 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). IEEE, 2012. http://dx.doi.org/10.1109/fskd.2012.6233708.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Martinek, Pavel. "Fuzzy multiset finite automata: Determinism, languages, and pumping lemma." In 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). IEEE, 2015. http://dx.doi.org/10.1109/fskd.2015.7381915.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Gal-Ezer, Judith, and Mark Trakhtenbrot. "Challenges in teaching the pumping lemma in automata theory course." In the 10th annual SIGCSE conference. New York, New York, USA: ACM Press, 2005. http://dx.doi.org/10.1145/1067445.1067569.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Dharaneetharan, G. D., V. Brammanandha Raj, and R. Kanniga Devi. "An alternative approach of Pumping Lemma to prove a language to be non regular." In 2011 International Conference on Recent Trends in Information Technology (ICRTIT). IEEE, 2011. http://dx.doi.org/10.1109/icrtit.2011.5972352.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Johnsonbaugh, Richard, and David P. Miller. "Converses of pumping lemmas." In the twenty-first SIGCSE technical symposium. New York, New York, USA: ACM Press, 1990. http://dx.doi.org/10.1145/323410.319073.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Smith, Therese, and Robert McCartney. "Mathematization in teaching pumping lemmas." In 2013 IEEE Frontiers in Education Conference (FIE). IEEE, 2013. http://dx.doi.org/10.1109/fie.2013.6685122.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Pumping lemma' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography