Original title: Demonstrace skákajících automatů
Translated title: Demonstrations of Jumping Automata
Authors: Růžička, Ladislav ; Kocman, Radim (referee) ; Křivka, Zbyněk (advisor)
Document type: Bachelor's theses
Year: 2017
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce se zabývá demonstrací nově zkoumaného výpočetního modelu pro popis formálních jazyků, a to skákajícího automatu. Místo souvislého čtení vstupního řetězce, jak je tomu u konvenčních konečných automatů, tak u skákajícího automatu je proveden skok přes nějaké symboly, a poté je přečten symbol. V této práci se zejména budeme zabývat hledáním praktického algoritmu pro určení problému členství vstupního řetězce do jazyka popsaného skákajícím automatem. Ukážeme, že problém členství může být redukován na problém hledání nějakého nezáporného celočíselného řešení pro formuli v Presburgové aritmetice bez kvantifikátorů. Z této formule jsme schopni jednoznačně definovat jazyk přijímaný skákajícím automatem. Najdeme podmnožinu takových skákajících automatů, pro které lze vyřešit problém členství v polynomiálním čase. Zmíníme se také, že předchozí formule lze převést na konečný automat s více čtecími hlavami. Bohužel pro problém členství obecného skákajícího automatu hledání nezáporné číselného řešení je nedostačující, nicméně metoda může zmenšit prohledávaný stavový prostor. Uvedeme další možné heuristiky, které výrazně urychlují výpočet problému členství pro obecné skákající automaty. This paper is concerned with demonstration of newly investigated jumping finite automata. Unlike conventional finite automata that read input words continuously these automatas make a jump over some symbols and from there it can read a symbol. In this paper we will be mostly focused on finding a practical algorithm for solving the membership problem. As will be shown the membership problem for jumping finite automata can be reduced to finding a non-negative integral solution to a Quantifier-Free Presburger arithmetics formula. From such formula we are able to determine whole infinite language of jumping finite automata. We will show that some subset of jumping finite automata can be solved in polynomial time. We note that formula in Presburger arithmetics can be transformed to the corresponding concurent finite automata. Unfortunately for general jumping automata finding non-negative solution is not sufficent but it can reduce search space. Other heuristics will be presented that increase the effectivity for the general jumping finite automata acceptance process.
Keywords: backtrack; constraint integer programming; general jumping finite automata; heuristics; integer linear programming; jumping finite automata; membership problem; celočíselné linearní programování; heuristiky; obecný skákající automat; podmínkové celočíselné programování; problém členství; skákající konečný automat; zpětné navrácení

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/69461

Permalink: http://www.nusl.cz/ntk/nusl-363767


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses