Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Numbers and Languages

Numbers and Languages

Tommi J. M. Lehtinen, Numbers and Languages. TUCS Dissertations 158. University of Turku, 2013.

Abstract:

The thesis presents results obtained during the authors PhD-studies. First systems of language equations of a simple form consisting of just two equations are proved to be computationally universal. These are systems over unary alphabet, that are seen as systems of equations over natural numbers. The systems contain only an equation X+A=B and an equation X+X+C=X+X+D, where A, B, C and D are eventually periodic constants. It is proved that for every recursive set S there exists natural numbers p and d, and eventually periodic sets A, B, C and D such that a number n is in S if and only if np+d is in the unique solution of the abovementioned system of two equations, so all recursive sets can be represented in an encoded form. It is also proved that all recursive sets cannot be represented as they are, so the encoding is really needed.

Furthermore, it is proved that the family of languages generated by Boolean grammars is closed under injective gsm-mappings and inverse gsm-mappings. The arguments apply also for the families of unambiguous Boolean languages, conjunctive languages and unambiguous languages.

Finally, characterizations for morphisims preserving subfamilies of context-free languages are presented. It is shown that the families of deterministic and LL context-free languages are closed under codes if and only if they are of bounded deciphering delay. These families are also closed under non-codes, if they map every letter into a submonoid generated by a single word. The family of unambiguous context-free languages is closed under all codes and under the same non-codes as the families of deterministic and LL context-free languages.

Files:

Full publication in PDF-format

BibTeX entry:

@PHDTHESIS{phdLehtinen_TommiJxMx13a,
  title = {Numbers and Languages},
  author = {Lehtinen, Tommi J. M.},
  number = {158},
  series = {TUCS Dissertations},
  school = {University of Turku},
  year = {2013},
  ISBN = {978-952-12-2849-0},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication