Semilineaariset

Semilineaariset (semilineaariset joukot) ovat osajoukkoja N^k:sta, jotka ovat finittisen union lineaarisista joukoista. Lineaarinen joukko L(b; p1, ..., pn) koostuu kaikista muodoista b + t1 p1 + ... + tn pn, missä t_i ∈ N. Tässä b ∈ N^k on perusvektori ja p_i ∈ N^k ovat periodivektoreita.

Semilineaarinen joukko S on siten finittisen monta lineaarisen muotoa yhdistävä joukko: S = ⋃_{j=1}^m L(b_j; p_{j1}, ..., p_{jn_j}). Tämä rakenne mahdollistaa joukon eksplisiittisen kuvauksen ja ennustettavuuden.

Sovellukset ja yhteydet: Semilineaariset joukot ovat keskeisiä automaatioteoriassa ja kielitieteessä. Parikhin teoreeman mukaan kaikkien kontekstuaalisten kielten Parikh-kuvat ovat semilineaarisia; Parikh-kuva tallentaa sanan symbolien lukumäärät, eikä niiden järjestystä.

Ominaisuudet: Semilineaariset joukot ovat suljettuja useimpien tavallisten operaatioden, kuten liitoksen, leikkauksen ja projektioiden, parissa. Niitä voidaan tulkita Presburger-lyhenteinä, ja ne vastaavat kaikkia määriteltyjä kokonaislukukuvauksia.

Esimerkkejä: N^2 on semilineaarinen. Esimerkki lineaarisesta joukosta on { (t, t) | t ∈ N }, jonka perusvektori on (0,0) ja yksittäinen periodi (1,1). Myös joukko { (x,y) ∈ N^2 | x + y = k } on semilineaarinen, kun k on vakio.

Konteksti: Semilineaariset kuvaukset esiintyvät laajasti teoria­tietojenkäsittelyssä ja diskreetissä matematiikassa, tarjoten työkalun lukumäärä- ja koostumusrakenteiden analysointiin.