Semigroups, groups and grammar inference problem

• Autorzy: Skolicki Z.

Warianty tytułu

PL

Półgrupy, grupy i zagadnienie wnioskowania gramatycznego

• Języki publikacji: EN

Abstrakty

EN

In the paper we analyse a problem of inferring a grammar from a given sample of a language. We try to present an algebraic formalism capable of describing the issue. We consider two cases: a case of inferring canonical finite-state grammars, and a case of inferring general grammars. In both cases we define a semigroup structure. Finally we look at the possibility of getting a structure of a group.

PL

Praca omawia problem wnioskowania gramatycznego na podstawie próbki języka. Problem przedstawiony jest w kontekście algebraicznym, poprzez próbę stworzenia adekwatnego formalizmu opisującego to zagadnienie. W pracy rozważone są dwa przypadki - kanonicznej gramatyki regularnej oraz ogólnej gramatyki. Dla obu podproblemów stworzony został opis używający półgrup. W końcowej części pracy rozważamy możliwość opisania wnioskowania gramatycznego przy użyciu grup.

Słowa kluczowe

EN

grammar inference; semigroup; group

PL

wnioskowanie gramatyczne; półgrupy; grupy

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2002
• Tom: Vol. 4
• Strony: 39--54
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Skolicki Z.

• Institute of Computer Science, Jagiellonian University, Cracow,

Bibliografia

• [1] Fu K.S.: Syntactic Pattern Recognition and Applications. New Jersey, Prentice-Hall, Inc. 1982
• [2] Aho A.V., Ullman J.D.: The Theory of Parsing, Translation and Compling. Englewood Cliffs, N.J., Prentice-Hall, Inc. 1972
• [3] Chomsky N.: Syntactic Structures. The Hague, Mouton Publishers 1957
• [4] Hopcroft J.E., Ullman J.D.: Formal Languages and Their Relation to Automata. Reading, MA, Addison-Wesley 1969
• [5] Skolicki Z.: Semigroups and automata. ZN UJ (to be printed)