A kongruenciális nyelv egy hivatalos nyelv, amely a kongruencia véges számú osztályának egyesülése az adott ábécén. Fontos eset, amikor a kongruenciát egy véges átírási rendszer generálja . Attól függően, hogy milyen típusú újraírás rendszer, a algoritmikus komplexitása a szót probléma lehet lineáris időben, PSPACE-teljes, vagy eldönthetetlen.
A kongruenciális nyelvi osztályok a nyelvek másik hierarchiáját alkotják, összehasonlíthatatlanul Chomsky hierarchiájával .
A újraírás rendszer egy véges ábécé A véges halmaza pár szót az A , az úgynevezett újraírás szabályok bemutatott formában . Az ilyen rendszert néha fél-Thue rendszernek vagy fél-Thue rendszernek is nevezik . A rendszer hossza csökken, ha valamilyen szabályt alkalmazna. Ez Church-Rosser ha egybefolyó , vagy ha azonos módon, ellenőrzi az egyház Rosser tulajdonság .
A hivatalos nyelv L jelentése kongruencia , ha létezik egy véges újraírás rendszer S oly módon, hogy az L egy véges unió osztályainak modulo congruences S. szerint a tulajdonságait az újraírás rendszer, az osztály kongruencia nyelv többé-kevésbé korlátozott.
Egy L nyelv van kongruencia Church-Rosser ha L egy véges unió osztályainak congruences modulo csökkenő Church-Rosser újraírás rendszer.
A paradigmatikus példája Dyck nyelvet egy pár betűt . Ez a nyelv alkotja szavai egy osztály a kongruencia által generált , azaz az osztály üres szó.
A Congruential Church-Rosser nyelvek osztályát 1988-ban vezették be McNaughton, Narendran és Otto.
A nyelvek ezen osztályának tanulmányozásának egyik legfőbb motivációja, hogy a tagsági probléma lineáris időben megoldható: egy Church-Rosser rendszerben minden osztálynak egyedi visszavonhatatlan eleme van; amikor a rendszer tovább csökken, minden szó esetében a szó normál alakja kiszámítható a szó szabály szerinti csökkentésével, akkor elegendő tesztelni, hogy a csökkentett szó szerepel-e a az osztályok, amelyeknek nyelve a találkozás.
Ennek a tesztnek a végrehajtásához ezért nem szükséges, hogy az által generált kongruencia monoid hányadosa véges legyen, csak az osztályok száma lehet véges.
Dyck nyelvének, Lukasiewicz nyelvének példáján kívül az egyház-Rosser nyelv kongruens (utóbbi esetében a redukciót a szabály hajtja végre ); a nyelv nem. A palindromok nyelve nem Church-Rosser. A determinisztikus algebrai nyelv nem mindig egybevágó Church-Rosser. McNaughton, Narendran és Otto meghatároz egy általánosabb nyelvcsaládot, amelyet „CRDL-nek” neveznek, az eldönthető Church-Rosser nyelvek számára, és megmutatják, hogy minden determinisztikus algebrai nyelv eldönthető Church-Rosser .
Sokáig sejtették azt a tulajdonságot, hogy minden racionális nyelv Church-Rosser kongruenciális . 2012-ben demonstrációt hirdettek az ICALP konferencián, majd 2015-ben tették közzé.
Korábban, 2003-ban, Klaus Reinhardt és Denis Thérien bejelentették, hogy minden racionális nyelv, amelynek szintaktikai monoidja egy csoport, egybevágó Church-Rosser, de ezt a cikket nem publikálták felülvizsgálatban, és a helyesség kétséges.
Volker Diekert, Manfred Kufleitner és Pascal Weil 2012-ben publikált közbenső eredménye azt mutatja, hogy minden csillag nélküli nyelv Church-Rosser kongruenciális. Ehhez a szerzők bebizonyítják, hogy bármely csillag nélküli nyelv esetében létezik olyan véges Church-Rosser átírási rendszer, amely véges számú egyenértékűségi osztály egyesülése, és amelynek további figyelemre méltó tulajdonsága van, hogy minden szabályhoz , a joghoz tag ' a bal tag alszava , azaz bizonyos betűk eltávolításával nyerhető . Ez a tulajdonság az általános esetre a következőképpen bővül: A súlyfüggvény olyan függvény, amely minden betűhöz pozitív egész számot társít, és amelyet kiegészítenek a szavakra is. Az átírási rendszer súlya reduktív, ha bármilyen szabályra van is .
Bármely racionális nyelve az , létezik egy véges, összefüggő és testsúlycsökkentő újraírás rendszer olyan, hogy a hányados monoid véges, és elismeri .Ez a tulajdonság a racionális nyelvek új jellemzését adja.
Egy kevésbé korlátozó átírási rendszert közeli összefolyási rendszernek neveznek . A rendszer szinte torkolatánál, ha bármely két azonos szavakkal, két szó van , és az azonos hosszúságú és és és átírható egymásba szabályok megőrzése hosszát.
A csaknem összefolyó egybevágó nyelv olyan nyelv, amely a szinte összefolyó kongruencia osztályainak véges egyesítése. Míg a tagsági probléma lineárisan összetett egy csökkenő Church-Rosser rendszer esetében, a PSPACE teljes a majdnem összefolyó rendszereknél.
Könnyen belátható, hogy minden racionális nyelv szinte összefolyik. Legyen tulajdonképpen a racionális nyelve . Létezik egy véges monoid egy szürjektıv morfizmus a szóló , és egy része az ilyen , hogy
.Nézzük jelent számára az . A partíció részekre , mert itt lehet tenni egy majdnem teljesen összefolyt átíró rendszer, az alábbiak szerint: Az összes az , akár egy elem minimális hosszúságú , és vagy a maximális hossza szavak . A párok S rendszere
szinte összefolyó rendszer, és a kongruenciák osztályai egybeesnek a részekkel .
A racionális nyelvek ez a tulajdonsága kevésbé pontos, mint Church-Rosseré, és valóban vannak szinte egybevágó, egybevágó nyelvek, amelyek nem egybehangzóak Church-Rosser-nel. Ilyen például Colm Ó Dúnlaing. Az ábécé tekintetében figyelembe vesszük a for által generált kongruenciát és a szabályokat . Az S által definiált egybevágóság a kongruencia alapján valójában a relatív egész számok gyűrűje , és a nyelv , ennek fordított képe , olyan szavakból áll, amelyeken annyi betű van áthúzva, ahányan nincsenek áthúzva. Ez a nyelv szinte összefolyik, és nem Church-Rosser kongruenciális.