University of Oulu

Very small families generated by bounded and unbounded context-free languages

Saved in:
Author: Salmi, Tuukka1,2
Organizations: 1University of Oulu, Faculty of Science, Department of Mathematical Sciences
2University of Oulu, Infotech Oulu
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, 0.8 MB)
Persistent link:
Language: English
Published: 2009
Publish Date: 2009-11-04
Thesis type: Doctoral Dissertation
Defence Note: Academic dissertation to be presented with the assent of the Faculty of Science of the University of Oulu for public defence in Raahensali (Auditorium L10), Linnanmaa, on 14 November 2009, at 12 noon
Reviewer: Professor Jean-Michel Autebert
Professor Michel Latteux


In this thesis, we will study very small full trios and full AFLs inside the family of context-free languages. Especially, we are interested in the existence of the smallest nontrivial full trios and full AFLs. This is an old research subject, and it has not been studied much since the 1970s. A conjecture by Autebert et al. states that there does not exist a nontrivial minimal full trio inside the family of context-free languages (2) (see also (1)). First, we will show that there does not exist a nontrivial minimal full trio or a nontrivial minimal full AFL with respect to the bounded context-free languages. This result solves another old conjecture stated by Autebert et al. (1). Then we will try to generalize our result to also concern unbounded context-free languages. We will make some progress, but the problem still remains open.

see all

Series: Acta Universitatis Ouluensis. A, Scientiae rerum naturalium
ISSN-E: 1796-220X
ISBN: 978-951-42-9274-3
ISBN Print: 978-951-42-9273-6
Issue: 536
Copyright information: © University of Oulu, 2009. This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.