Skákající konečné automaty

Od Petr Zemek, 2013-02-10

10. prosince 2012 jsem měl společně s prof. Medunou úvodní přednášku na studentské konferenci Language Theory With Applications 2012 na téma "Skákající konečné automaty". O čem tato přednáška byla, kde můžete zhlédnout (konečně zveřejněný) záznam a kde si lze stáhnout materiály se dozvíte v následujícím krátkém příspěvku.

O čem tato přednáška byla?

Přednáška vycházela z našeho společného článku Jumping Finite Automata, který nedávno vyšel v časopise International Journal of Foundations of Computer Science. Zavedli jsme v něm modifikaci konceptu konečného automatu, který nyní místo toho, aby četl vstupní pásku zleva doprava, symbol po symbolu, tak může po přečtení symbolu skočit na jakékoliv místo na pásce a pokračovat ve výpočtu odtud. Tato poměrně přirozená modifikace má však poměrně dalekosáhlé důsledky, ať co se týče přijímající síly, tak vlastností takto modifikovaných konečných automatů.

V přednášce jsme tuto modifikaci nejdříve vysvětlili a formálně definovali. Definici jsme pak ilustrovali na dvou příkladech. Následně jsme se vrhli na studium vlastností těchto automatů, a to konkrétně přijímající síly, konverzí, uzávěrových vlastností, omezení skoků doprava či doleva a různých počátečních konfigurací. Na závěr jsme shrnuli hlavní otevřené problémy a diskutovali toto téma s publikem.

Pokud vás téma přednášky zaujalo a budete mít večer chvilku čas, určitě mrkněte na záznam (viz níže). Abyste si přednášku užili, tak stačí, že víte, co je to a jak pracuje konečný automat a nebojíte se trochu matematična :).

Kde si můžu stáhnout záznam a doplňující materiály?

Tady:

Dále, pokud by to někoho zajímalo, tak část mých přednášek a prezentací je ke stažení zde (záznam je však jen z několika prezentací). Pokud vás něco zaujme, ozvěte se mi :).

Obsah tohoto pole je soukromý a nebude veřejně zobrazen.

Filtrované HTML (využíváno)

  • Povolené HTML značky: <a href hreflang> <em> <strong> <cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <table>
  • Zvýraznění syntaxe kódu lze povolit přes následující značky: <code>, <blockcode>, <bash>, <c>, <cpp>, <haskell>, <html>, <java>, <javascript>, <latex>, <perl>, <php>, <python>, <ruby>, <rust>, <sql>, <text>, <vim>, <xml>, <yaml>.
  • Řádky a odstavce se zalomí automaticky.
  • Webové a e-mailové adresy jsou automaticky převedeny na odkazy.
CAPTCHA
8 + 6 =
Vyřešte tento jednoduchý matematický příklad a vložte výsledek. Např. pro 1+3 vložte 4.
Nějak se mi tady rozmohl spam, takže poprosím o ověření.