Memetski algoritem za sklepanje o kontekstno neodvisnih gramatikah in njegova uporaba pri načrtovanju domensko specifičnega jezika

doktorska disertacija

Dejan Hrnčič (Avtor), Marjan Mernik (Mentor)

Povzetek

V doktorski disertaciji predstavimo memetski algoritem za sklepanje o kontekstno neodvisnih gramatikah MAGIc. Memetski algoritem predstavlja evolucijski algoritem z vključenim operatorjem lokalnega iskanja. Sklepanje o gramatikah spada na področje strojnega učenja in predstavlja družino metod, kina podlagi pozitivnih in opcijsko negativnih vhodnih primerov določi strukturo oz. izpelje gramatiko. Algoritem MAGIc sklepa o kontekstno neodvisnih gramatikah samo na podlagi pozitivnih primerov, čeprav lahko v postopek sklepanja vključimo tudi negativne primere. Pri sklepanju uporablja kot dodatno znanje razlike med primeri, katere uporabi za razširitev obstoječih gramatik, da razpoznajo več vhodnih primerov. Algoritem smo testirali na množici domensko specifičnih jezikov, napravili primerjavo z algoritmom TBL in ga razširili z možnostjo vključevanja nove sintakse v obstoječo gramatiko splošnonamenskega jezika. Algoritem se je izkazal kot uspešen za sklepanje o kontekstno neodvisnih gramatikah domensko specifičnih jezikov in je neodvisen od zaporedja vhodnih primerov. Ključna operatorja algoritma sta lokalno iskanje in generalizacija.

Ključne besede

sklepanje o gramatikah;memetski algoritmi;domensko specifični jeziki;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2012
Izvor:	[Maribor
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	D. Hrnčič]
UDK:	004.855.2(043.3)
COBISS:	261202944
Št. ogledov:	1979
Št. prenosov:	175
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	ǂA ǂmemetic algorithm for context-free grammar inference and its use in domain-specific language design
Sekundarni povzetek:	In this dissertation a memetic algorithm for context-free grammar inference MAGIc (Memetic Algorithm for Grammatical Inference) is presented. A memetic algorithm is an evolutionary algorithm with embedded local search. Grammaticalinference belongs to the field of machine learning and represents aset of methods that infer grammars based on positive and optionally negative samples. The algorithm MAGIc is capable of inferring context-free grammars from positive samples only, although we can also provide negative samples as algorithm input. To infer context-free grammar, the differences between positive samples are used to expand current grammar solutions in order to parse more positive input samples. The algorithm was tested on a set of domain-specific languages, a comparison with current 'state-of-the-art' algorithm TBL (tabular representation algorithm) was done and it was extended with an ability to embed domain-specific language constructs into an existing general purpose language grammar. The algorithm was proven to be successful for grammar inference of domain-specific languages and is independent of the input sample order. The most important algorithm operators are local search and generalization
Sekundarne ključne besede:	Strojno učenje;Disertacije;Konteksno neodvisne gramatike;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Doktorska disertacija
Komentar na gradivo:	Univ. v Maribor, Fak. za elektrotehniko, računalništvo in informatiko
Strani:	XII, 150 str.
Ključne besede (UDK):	science and knowledge;organization;computer science;information;documentation;librarianship;institutions;publications;znanost in znanje;organizacije;informacije;dokumentacija;bibliotekarstvo;institucije;publikacije;prolegomena;fundamentals of knowledge and culture;propaedeutics;prolegomena;splošne osnove znanosti in kulture;computer science and technology;computing;data processing;računalniška znanost in tehnologija;računalništvo;obdelava podatkov;artificial intelligence;umetna inteligenca;
ID:	1017291