Refine
Document Type
- Article (1)
- Part of a Book (1)
- Doctoral Thesis (1)
- Preprint (1)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Keywords
- Formale Sprache (4) (remove)
Institute
- Extern (1)
- Informatik (1)
Im Gegensatz zur Minimierung von DFAs ist die exakte Minimierung von NFAs oder regulären Ausdrücken nachweislich schwierig, im allgemeinen Fall PSpace-schwer. Wir zeigen, dass selbst schwache Approximationen zur Minimierung von NFAs und regulären Ausdrücken wahrscheinlich nicht effizient möglich sind. Falls als Eingabe ein NFA oder regulärer Ausdruck der Größe n gegeben ist, löst ein Approximationsalgorithmus für das Minimierungsproblem mit Approximationsfaktor o(n) bereits ein PSpace-vollständiges Problem. Wenn wir uns auf NFAs oder reguläre Ausdrücke über einem unären - also einelementigen - Alphabet beschränken, so ist das Problem der exakten Minimierung NP-vollständig. Wir weisen nach, dass effiziente Approximationen für das unäre Minimierungsproblem mit Approximationsfaktor n^(1-delta) für jedes delta>0 nicht möglich sind, sofern P != NP gilt. Liegt die Eingabe als DFA mit n Zuständen vor, kann sie exponentiell größer sein als ein äquivalenter NFA oder regulärer Ausdruck. Dennoch bleibt das Minimierungsproblem PSpace-schwer, wenn die Anzahl der Übergänge oder Zustände in einem äquivalenten NFA oder die Länge eines äquivalenten regulären Ausdrucks zu bestimmen ist. Wir zeigen, dass auch hierfür keine guten Approximationen zu erwarten sind. Unter der Annahme der Existenz von Pseudozufallsfunktionen, die wiederum auf der Annahme basiert, dass Faktorisierung schwierig ist, zeigen wir, dass kein effizienter Algorithmus einen Approximationsfaktor n/(poly(log n)) für die Zahl der Übergänge im NFA oder die Länge des regulären Ausdrucks garantieren kann. Für die Zahl der Zustände im NFA weisen wir nach, dass effiziente Approximationen mit Approximationsfaktor (n^(1/2))/(poly(log n)) ausgeschlossen sind. Wir betrachten dann Lernprobleme für reguläre Sprachen als Konzeptklasse. Mit den entwickelten Methoden, die auf der Annahme der Existenz von Pseudozufallsfunktionen beruhen, zeigen wir auch, dass es für das Problem des minimalen konsistenten DFAs keine effizienten Approximationen mit Approximationsfaktor n/(poly(log n)) gibt. Für den unären Fall hingegen weisen wir nach, dass es einen effizienten Algorithmus gibt, der einen minimalen konsistenten DFA konstruiert und erhalten somit auch einen effizienten PAC-Algorithmus für unäre reguläre Sprachen, die von DFAs mit n Zuständen akzeptiert werden. Für unäre Beispielmengen weisen wir außerdem nach, dass es keine effizienten Algorithmen gibt, die minimale konsistente NFAs konstruieren, falls NP-vollständige Probleme nicht in Zeit (n^(O(log n)) gelöst werden können. Andererseits geben wir einen effizienten Algorithmus an, der zu unären Beispielmengen einen konsistenten NFA mit höchstens O(opt^2) Zuständen konstruiert, wenn ein minimaler konsistenter NFA opt Zustände hat. Abschließend betrachten wir das Lernen von DFAs durch Äquivalenzfragen. Für den nicht-unären Fall ist bekannt, dass exponentiell viele Fragen für DFAs mit n Zuständen benötigt werden. Für unäre zyklische DFAs mit primer Zykluslänge und höchstens n Zuständen zeigen wir, dass Theta((n^2)/(ln n)) Äquivalenzfragen hinreichend und notwendig sind. Erlauben wir größere zyklische DFAs als Hypothesen, kommen wir mit weniger Fragen aus: Um zyklische DFAs mit höchstens n Zuständen durch Äquivalenzfragen mit zyklischen DFAs mit höchstens n^d Zuständen für d <= n als Hypothesen zu lernen, sind O((n^2)/d) Fragen hinreichend und Omega((n^2 ln d)/(d (ln n)^2)) Fragen nötig.
This paper investigates the relation between TT-MCTAG, a formalism used in computational linguistics, and RCG. RCGs are known to describe exactly the class PTIME; simple RCG even have been shown to be equivalent to linear context-free rewriting systems, i.e., to be mildly context-sensitive. TT-MCTAG has been proposed to model free word order languages. In general, it is NP-complete. In this paper, we will put an additional limitation on the derivations licensed in TT-MCTAG. We show that TT-MCTAG with this additional limitation can be transformed into equivalent simple RCGs. This result is interesting for theoretical reasons (since it shows that TT-MCTAG in this limited form is mildly context-sensitive) and, furthermore, even for practical reasons: We use the proposed transformation from TT-MCTAG to RCG in an actual parser that we have implemented.
Ortak ve Suni dil üzerine
(2013)
Ortak ve Suni dilin ayrıştığı nokta bir toplum içerisinde bireylerin sağlıklı iletişim kuramamaları sonucu birbirlerini anlamadıkları ve iletişimin abartılı bir durumda değerlendirilmesidir. Bireyler arasında sağlıklı iletişimin sağlanması, aralarında ihtilafın giderilmesi gibi konular dilbilimcilerin başlıca araştırma alanlarını oluşturmaktadır. Diğer bir ifade ile yapay dil ile ortak bir dilin amaçlanması, geliştirilmesi 16.y.y. dan itibaren günümüze değin sürdürülmüştür. Ne var ki konuyu sadece art zamanlı olarak değerlendirmek yerine, aynı toplum içerisinde eş zamanlı olarak nasıl irdelenebilir? Zira ortak dilin "evrensel" bir dil olduğu varsayımından hareketle aynı toplum içerisinde, iletişimin genellikle "yapay" bir dille gerçekleştiği savını da öne sürebiliriz. Bir toplum içerisinde ortak dile ulaşmanın yolu analiz-sentez yolu ile kavrama kültürünün doğru orantılı olmasıdır.
Türkçe, Almanca, İngilizce gibi doğal dillerde bir tümce temelde özne ve yüklemden oluşur. Benzer şekilde biçimsel dillerde de bir tümce, yüklem ve argümandan oluşur. Yüklemler P, Q, R gibi büyük harflerle, argümanlar ise x, y, z gibi küçük harflerle gösterilir. Örneğin olumlu bir tümce P(x), olumsuz bir tümce ise -P(x) şeklinde ifade edilebilir. Ancak bazen bir tümcenin olumlu mu yoksa olumsuz mu olduğu net bir şekilde belli olmayabilir. Bu tür durumlarda mevcut sembolik gösterimde belirsizlikler ortaya çıkabilmektedir. Olumlu tümcelere matematiksel olarak 1, olumsuz tümcelere ise 0 değerinin verildiği varsayılırsa, olumluluk veya olumsuzluk durumu belirsiz olan tümceler ancak bu iki değer arasında bir değer alabilir. Diğer bir deyişle P(x) şeklinde gösterilebilen bir tümceyi P1(x), -P(x) şeklinde gösterilen bir tümceyi ise P0(x) şeklinde ifade etmek mümkündür; fakat olumluluğu kesin olmayan tümceler bu değerlerle gösterilemeyeceği için başka bir ifade şekline ihtiyaç vardır. Çünkü bu tümcelerdeki iş, oluş veya hareketin gerçekleşme oranı ne 0 ne de 1'dir; 0 ve 1 arasında bir değerdir. Bu çalışmada bu tür tümcelerin biçimsel dillerde nasıl ifade edilebileceğine dair bir öneride bulunmak ve bulanık küme kuramıyla olumluluğu derecelendirmek amaçlanmıştır. Bu amaç doğrultusunda önerilen yaklaşım birtakım örnek tümceler üzerinde uygulanmış ve söz konusu tümceler bulanık sembolik bir gösterimle ifade edilmiştir.