225 KB15 KB200820252017Archdeacon, Dan StevenBokal, DragoGologranc, Tanjaštevilka:1letnik:12str. 31-36ISSN:1855-3966COBISSID:22049288URN:URN:NBN:SI:doc-LNMCXL1CenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadobra karakterizacijaGaussove besedeGaussove kodeGaussovi paragrafiiA characterization of plane Gauss paragraphs|Gauss first studied representations of self-intersecting curves in the plane using only lists of their crossings in the sequence as they occur when traversing a curve, i.e., representations using Gauss words. The characterisation of words that are Gauss words has been elusive for a long time, and only in recent decades have some good characterizations been established. Together with these, the interest in Gauss paragraphs, i.e., representations of sets of curves by sets of words listing their sequences of crossings, has came to light, and we are unaware of a (good) characterization of abstract sets of words that are Gauss paragraphs. We establish such a characterization and we show that characterizing Gauss paragraphs is algorithmically equivalent to characterizing Gauss words, as there exists a word ?$W$? that can be obtained from a set of words ?$P$? in linear time, such that ?$P$? is a Gauss paragraph if and only if ?$W$? is a Gauss wordGauss je prvi študiral reprezentacije samo-sekajočih se krivulj v ravnini zgolj s pomočjo seznamov njihovih križišč v zaporedju, kot jih srečujemo, ko potujemo po krivulji, t.j. reprezentacij z uporabo Gaussovih besed. Karakterizacija besed, ki so Gaussove, je bila dolgo odprt problem in šele v zadnjih desetletjih je bilo odkritih nekaj dobrih karakterizacij. Obenem s tem se je okrepilo zanimanje za Gaussove paragrafe, t.j. reprezentacije množic krivulj z množicami besed, ki navajajo njihova zaporedja križišč. Ne zavedamo se nobene (dobre) karakterizacije abstraktnih množic besed, ki so Gaussovi paragrafi. Podamo takšno karakterizacijo in pokažemo, da je karakterizirati Gaussove paragrafe algoritmično ekvivalentno karakterizaciji Gaussovih besed, saj obstaja beseda ?$W$?, ki jo lahko dobimo iz množice besed ?$P$? v linearnem času, tako da je ?$P$? Gaussov paragraf, če in samo če je ?$W$? Gaussova besedaTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije