A characterization of plane Gauss paragraphs

angleški

2017

letnik 12, številka 1

dobra karakterizacija   Gaussove besede   Gaussove kode   Gaussovi paragrafii

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Gauss 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 beseda.

29.05.2020