Szerintem:
(1.) az érdekes lenne, ha 0-ás nyelvtanokhoz találsz olyan algoritmust, amely a mondatok nagy részére, elfogadható idő alatt talál levezetést.
(Mondjuk a 'mondatok nagy része' kifejezést te nem fogod érteni, mert azt mondod, hogy végtelen mondat van, ha ebből végesről nem dönti el, akkor ..., egyébként meg végtelen/végtelen. )
(2.) az is érdekes lenne, ha tudnál mondani a 0-ás nyelvtanokhoz egy olyan normálformát, amiről egyszerű eldönteni, hogy készíthető-e hozzájuk hatékony algoritmus a tartalmazás probléma eldöntésére.
Ha jól értem, Te komplexitáselméleti problémákat kötsz össze formális nyelvelméleti problémákkal.
A megközelítésed alkalmazás-jellegű, ez nem baj, csak nem legyen kizárólagos. Túl biztos vagy magadban.
Persze, nagyon érdekes, ha igazoljuk (ZFC-ben:)), hogy P-ben van mondjuk egy kanonikusan PSPACE-beli eldöntési algoritmust használó nyelv. Ez erős eredmény. Vagy lineáris idejű algoritmussal oldható meg egy 0-adrendű grammatikával generált, de rekurzív nyelv szóproblémája.
Ugyanígy ez a témakör az approximáció, közelítő algoritmusok kérdése. Ez nem klasszikus formális nyelvelmélet.
Én nagyon szeretem a komplexitáselméletet, a P?=NP-problémát, és hasonlókat. Ezekre külön van topik.
Valójában MINDEN komplexitáselméleti probléma átfogalmazható nyelvészetivé, hiszen automaták különböző tárral, és időben döntenek el (ha eldöntenek) nyelveket.
Ez azonban már két matematikai ág, az algoritmikus komplexitáselmélet, és a formális nyelvészet összekapcsolódása.
A formális nyelvészet azonban ennél több.
Az, hogy létezik-e algoritmus az ABC problémára, nem érdekes
Ha tudod, hogy nem létezik algoritmus, keresel lineáris idejűt?:)
Az egzisztenciális bizonyítások alapvetően nem érdekesek
Jó, hogy ezt Te így tudod. Jó konstruktivista matematikus lennél: ott ugyanis egy egzisztencia-bizonyításhoz mindig van konstruktív is.:)
|