Advanced Studies on the Complexity of Formal Languages

Abstract

Tutkimuksia formaalien kielten laskennallisesta vaativuudesta

Laskennan monimutkaisuudella tarkoitetaan niiden resurssien määrää, jotka tarvitaan tietyn laskentatehtävän ratkaisemiseen. Laskennassa tarvittavia resursseja ovat aika (laskenta-askelten lukumäärä), muistitila, käytettävän laitteiston monimutkaisuus ja laskentayksikköjen välisen kommunikaation määrä. Laskennan monimutkaisuuden teoriassa (kompleksisuusteoriassa) etsitään minimaalisia resursseja annettujen laskenta-tehtävien ratkaisemiseen. Tietyssä laskentamallissa tarvittavien resurssien määrä jakaa ongelmat vaativuusluokkiin. Samaan vaativuusluokkaan kuuluvat ongelmat voidaan siis ratkaista tarkasteltavassa laskentamallissa kutakuinkin samoilla resursseilla.

Tässä väitöskirjassa tutkitaan formaalien kielten vaativuusluokkia. Erityisesti tarkastellaan sellaisia kieliperheitä, jotka voidaan tunnistaa alilineaarisilla resursseilla. Kieliperheen tunnistaminen alilineaarisilla resursseilla edellyttää yleensä rinnakkaislaskentaa, ja tämän vuoksi tutkimuksessa käytetään pääasiallisena laskennan mallina ns. alternoivaa Turingin konetta, jonka määräämiä vaativuusluokkia kutsutaan nimellä ALOGTIME. Muina malleina käytetään tavallista Turingin konetta, monilaskurikonetta ja branching programs -mallia.

Generoivina malleina tarkastellaan Chomskyn kielioppeja, ohjattuja uudelleenkirjoitusjärjestelmiä (regulated rewriting systems) ja kielioppijärjestelmiä (grammar systems). Näihin kaikkiin liitetään ns. Szilardin kieli, joka kuvaa johtojen muotoa määräämällä kielen, jonka lauseet muodostuvat generoivan järjestelmän sääntöjen yksikäsitteisistä nimistä.

Chomskyn kielten osalta todistetaan yläraja NC1 rajoittamattomien johtojen ja vasempien johtojen Szilardin kielille. Lisäksi annetaan uusi todistus Chomskyn-Schützenbergin lauseelle. Tähän liittyen esitellään myös uusi normaalimuoto kontekstittomille kieliopeille; tästä käytetään nimitystä Dyckin normaalimuoto.

Ohjattuihin kielioppijärjestelmiin liittyen tutkitaan matriisikielioppeja, satunnaisen kontekstin kielioppeja (random context grammars) ja ohjelmoituja kielioppeja (programmed grammars). Kaikkein näiden kohdalla todistetaan uusia tuloksia rajoittamattomiin ja vasempiin johtoihin liittyvien Szilardin kielten tunnistamiseen kuluville resursseille.

Kielioppijärjestelmiin liittyen tarkastellaan resurssivaatimuksia, jotka kuvaavat tarvittavaa kommunikaation ja yhteistyön määrää.

In the fields of computer science, mathematics, statistics, (bio)physics, or in any other science that requires mathematical approaches, complexity estimates the computational resources needed by a device to resolve a problem. Almost in all scientific fields, computational processes are measured in terms of time (steps or elementary operations), space (memory), circuitry (nets or hardware) and more recently communication (amount of information).

This dissertation encompasses results obtained by the author in the area of the complexity of formal languages. We focus on classes of languages of low complexity, where low complexity means sublinear resources. In general, low level complexity can be reached via parallel computation, and therefore the main computational model used throughout this thesis is the indexing alternating Turing machine. This hybrid model defines the so called ALOGTIME complexity class, which may be considered as a binder between circuitry, parallel, and sequential complexity classes.

The generative devices investigated in this dissertation are Chomsky grammars, regulated rewriting systems, and grammar systems. Each generative device has assigned a Szilard language, which in terms of labels associated with the rules or components, describes the derivations in the considered generator.

Chomsky grammars: We prove that certain Szilard languages associated with Chomsky grammars are contained in ALOGTIME. Additionally, we propose an alternative proof of the Chomsky-Schutzenberger theorem, based on a graphical approach, and we propose a new regular approximation method for context-free languages.

Regulated Rewriting Systems: We investigate the complexity of unrestricted and leftmost-like Szilard languages associated with matrix grammars, random context grammars, and programmed grammars. We prove that almost all these classes of languages are of low level complexity.

Grammar Systems: One of the most important dimensions of the real life is the capacity of communication. Communication is everywhere, expressed through the meaning of human languages or coding systems, communication between different parts of a computer, communication between agents and networks, communication in plants (cellular communication), in chemical or physical reactions. The parallelism applied to them will improve the communication performance, the time and space complexity, and the amount of information exchanged during the communication process. Grammar systems are formal devices that encompass some of these phenomena. In this dissertation we investigate two grammar system models, the parallel communicating grammar system and cooperating distributed grammar system.

The communication in parallel communicating grammar systems is based on request response operations performed by the system components through so called query symbols produced by query rules. Hence, the Szilard language associated with derivations in these systems is a suitable structure through which the communication can be visualized and studied. We prove that certain classes of Szilard languages associated with parallel communicating grammar systems are included in ALOGTIME.

To study the communication in cooperating distributed grammar systems, working under the classical derivation modes, we define several complexity structures (by means of cooperation and communication Szilard languages) and two complexity measures (the cooperation and communication complexity measures). We present trade-offs between time, space, cooperation, and communication complexity of languages generated by these grammar systems with regular, linear, and context-free components.

We also present simulations of cooperating distributed grammar systems, working in competence modes, by multicounter machines. As main consequences we reach (alternative) proofs of some decidability problems for these grammar systems and (through their generative power) for regulated rewriting grammars and systems.