Wyniki wyszukiwania - BazTech

1

Non-Self-Embedding Grammars and Descriptional Complexity

Pighizzini Giovanni, Prigioniero Luca

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 1-2

103--122

EN

Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s.

2

How to embed noncrossing trees in Universal Dependencies treebanks in a low-complexity regular language

Yli-Jyrä Anssi Mikael

Journal of Language Modelling

|

2019

|

Vol. 7, No. 2

177--232

EN

A recently proposed balanced-bracket encoding (Yli-Jyrä and Gómez-Rodríguez 2017) has given us a way to embed all noncrossing dependency graphs into the string space and to formulate their exact arcfactored inference problem (Kuhlmann and Johnsson 2015) as the best string problem in a dynamically constructed and weighted unambiguous context-free grammar. The current work improves the encoding and makes it shallower by omitting redundant brackets from it. The streamlined encoding gives rise to a bounded-depth subset approximation that is represented by a small finite-state automaton. When bounded to 7 levels of balanced brackets, the automaton has 762 states and represents a strict superset of more than 99.9999% of the noncrossing trees available in Universal Dependencies 2.4 (Nivre et al. 2019). In addition, it strictly contains all 15-vertex noncrossing digraphs. When bounded to 4 levels and 90 states, the automaton still captures 99.2% of all noncrossing trees in the reference dataset. The approach is flexible and extensible towards unrestricted graphs, and it suggests tight finite-state bounds for dependency parsing, and for the main existing parsing methods.

3

Infinite Hierarchy of Permutation Languages

Madejski G.

Fundamenta Informaticae

|

2014

|

Vol. 130, nr 3

263--274

EN

Permutation grammars are an extension of context-free grammars with rules having the same symbols on both sides but possibly in a different order. An example of a permutation rule of length 3 is ABC → CBA. If these non-context-free rules are of length at most n, then we say that permutation grammar is of order n and all such grammars generate a family of permutation languages Permn. In 2010 Nagy showed that there exists a language such that it cannot be generated by a grammar of order 2, but rules of length 3 are enough. In other words, a strict inclusion Perm2 \subsetneq Perm3 was obtained. We extend this result proving that Perm4n \minus 2 \subsetneq Perm4n \minus 1 for n ≥ 1.

4

On Normal Forms and Erasing Rules in Path Controlled Grammars

Koutnŷ J., Meduna A.

Schedae Informaticae

|

2013

|

Vol. 22

9--18

EN

This paper discusses path controlled grammars { context-free gram- mars with a root-to-leaf path in their derivation trees restricted by a control language. First, it investigates the impact of erasing rules on the generative power of path controlled grammars. Then, it establishes two Chomsky-like normal forms for path controlled grammars - the first allows unit rules, the second allows just one erasing rule.

5

Context-Free and E0L Derivations over Free Groups

Meduna A., Bildo R., Blatny' P.

Schedae Informaticae

|

2007

|

Vol. 16

9-20

EN

In the context-free and E0L grammars discussed in this pa- per, the derivations are introduced over free groups rather than free monoids. It is proved that both grammars with derivations introduced in this way characterize the family of recursively enumerable languages in a very succinct way. Specifically, this characterization is based on the eight-nonterminal context-free grammars and six-nonterminal E0L grammars over free groups.

6

Generowanie gramatyk bezkontekstowych dla potrzeb syntaktycznego rozpoznawania wzorców

Pałka D.

Informatyka Teoretyczna i Stosowana

|

2004

|

R. 4, nr 7

139-147

PL

W pracy tej przedstawiony został sposób automatyzacji procesu generowania gramatyk formalnych na podstawie pozytywnych i negatywnych przykładów języka. Sposób ten polega na ewolucji gramatyk w oparciu o technikę programowania genetycznego (GP). Może znaleźć on zastosowanie w procesie syntaktycznego rozpoznawania wzorców w przypadku, gdy reguły syntaktyczne nie są znane a priori, lecz muszą zostać określone na podstawie wzorców przykładowych. Jedną z dziedzin, w której istnieje zapotrzebowanie na tego typu wspomaganie i automatyzację procesu definiowania gramatyk jest syntaktyczna analiza wybranych typów obrazów medycznych dla potrzeb wspomagania diagnostyki różnego rodzaju schorzeń. W pracy przedstawione zostało porównanie rezultatów otrzymanych przy zastosowaniu w procesie ewolucji generatora analizatorów składniowych klasy GLR oraz klasy LALR(1) wykorzystanych do znalezienia gramatyki bezkontekstowej dla języka opisującego przewężenia tętnic wieńcowych.

EN

The article presents a method of automation of the grammatical inference process based on positive and negative language samples. The method makes use of the evolutionary approach based on genetic programming technique (GP) and can be used in the process of syntactic patterns recognition, especially in cases when syntactic rules are not known a priori but need to be induced on the basis of sample patterns. One of the areas in which such assistance and the automation of the grammatical inference process proves particularly useful is the syntactic analysis of selected types of medical images supporting diagnosis of various ailments. The advantages of the syntactic methods include greater generality and easier adaptability in comparison to the minima] distance methods which are commonly used in medical diagnosis. However, the application of the syntactic methods is not devoid of difficulties, the gravest of which being the actual finding of the grammar which would correctly classify images. The method of automation of the context-free grammars generation process based on language samples presented in this article is an attempt of solving this problem. The article presents the results obtained by applying Generalized LR (GLR) parsing algorithm to the evolution process, which allowed to avoid the difficulty of trying to make a language grammar fit the LALR(1) restrictions.

7

Ewolucyjne generowanie gramatyk bezkontekstowych z wykorzystaniem algorytmów genetycznych

Pałka D.

Elektrotechnika i Elektronika

|

2004

|

T. 23, z. 1

58-63

PL

Jedną z dziedzin, w której syntaktyczne metody rozpoznawania obrazu okazały się niezwykle użyteczne, jest analiza i wspomaganie diagnostyki niektórych schorzeń na podstawie określonych typów obrazów medycznych. Metody te cechują się większą ogólnością i elastycznością w porównaniu z powszechnie stosowanymi w diagnostyce medycznej metodami minimalno-odległościowymi. Jednak zastosowanie metod syntaktycznych wiąże się z dodatkowymi trudnościami, z których jedną z najważniejszych jest znalezienie odpowiedniej gramatyki pozwalającej na poprawne klasyfikowanie obrazów. W niniejszej pracy podjęta została próba automatyzacji procesu generowania gramatyk bezkontekstowych na podstawie zestawu słów należących do języka (przykładów pozytywnych) oraz słów nienależących do tego języka (przykładów negatywnych). Zaprezentowane podejście opiera się na technice algorytmów genetycznych z kodowaniem chromosomu, opisującego produkcje gramatyki w postaci drzewa.

EN

One of the areas in which syntactic pattern recognition methods have proved extremely useful is the analysis and the assistance of the diagnosis of some ailments on the basis of selected medical images. These methods are more general and more easily adaptable in comparison to the minimal distance methods which are commonly used in medical diagnosis. However, applying the syntactic base pattern recognition methods is not devoid of difficulties, the gravest one being the identification of the grammar allowing for the correct image classification. The paper attempts to automatise the process of generating context free grammars on the basis of the set of strings belonging to a given formal language (positive samples) and strings not belonging to this formal language (negative samples). The adopted approach is based on the genetic algorithm (GA) with direct encoding grammar production rules, which describes the production of the grammar in a tree form.