Готові списки джерел за темами / Pumping lemma

Добірка наукової літератури з теми "Pumping lemma"

Автор: Grafiati
Опубліковано: 10 грудня 2022
Оновлено: 28 січня 2023

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Зміст

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Pumping lemma".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
Більше джерел

Дисертації з теми "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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Анотація:
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 та ін.

Частини книг з теми "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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
Також вас можуть зацікавити розширені добірки на тему "Pumping lemma" для конкретних типів джерел:
Статті в журналах
Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!

До бібліографії