|
| |
|
|
Computational Bounded Rationality
Černý, Jakub ; Loebl, Martin (advisor) ; Hladík, Milan (referee)
This thesis formalizes a model of bounded rationality in extensive-form games called game-playing schemata. In this model, the strategies are repre- sented by a structure consisting of a deterministic finite automaton and two computational functions. The automaton represents a structured memory of the player, while the functions represent the ability of the player to identify efficient abstractions of the game. Together, the schema is a realization of a pure strategy which can be implemented by a player in order to play a given game. The thesis shows how to construct correctly playing schema for every pure strategy in any multi-player extensive-form game with perfect recall and how to evaluate its complexity. It proves that equilibria in schemata strategies always exist and computing them is PPAD-hard. Moreover, for a class of efficiently representable strategies, computing MAXPAY-EFCE can be done in polynomial time. 1
|
|
|
Library for Finite Automata and Transducers
Bieliková, Michaela ; Lengál, Ondřej (referee) ; Hruška, Martin (advisor)
Finite state automata are widely used in the field of computer science such as formal verification, system modelling, and natural language processing. However, the models representing the reality are complicated and can be defined upon big alphabets, or even infinite alphabets, and thus contain a lot of transitions. In these cases, using classical finite state automata is not very efficient. Symbolic automata are more concise by employing predicates as transition labels. Finite state transducers also have a wide range of application such as linguistics or formal verification. Symbolic transducers replace classic transition labels with two predicates, one for input symbols and one for output symbols. The goal of this thesis is to design a library for letter and symbolic automata and transducers which will be suitable for fast prototyping.
|
|
|
An Efficient Functional Library for Finite Automata
Říha, Jakub ; Hruška, Martin (referee) ; Lengál, Ondřej (advisor)
Finite automata are an important mathematical abstraction, and in formal verification, they are used for a concise representation of regular languages. Operations often used on finite automata in this setting are testing their universality and language inclusion. \mbox{A naive} approach to implement these operations leads to an explicit determinization of the automata, which can be costly and undesirable. There is, however, a more advanced method for performing those operations, called the Antichains algorithm, which avoids such an explicit determinization. This work shows how finite automata operations can be effectively implemented in Haskell and compares several approaches of their implementation. The obtained results are compared with VATA, an imperative implementation of a finite automata library.
|
|
|
Comparing Languages and Reducing Automata Used in Network Traffic Filtering
Havlena, Vojtěch ; Rogalewicz, Adam (referee) ; Vojnar, Tomáš (advisor)
The focus of this thesis is the comparison of languages and the reduction of automata used in network traffic monitoring. In this work, several approaches for approximate (language non-preserving) reduction of automata and comparison of their languages are proposed. The reductions are based on either under-approximating the languages of automata by pruning their states, or over-approximating the language by introducing new self-loops (and pruning redundant states later). The proposed approximate reduction methods and the proposed probabilistic distance utilize information from a network traffic. Formal guarantees with respect to a model of network traffic, represented using a probabilistic automaton are provided. The methods were implemented and evaluated on automata used in network traffic filtering.
|
|
|
Using hierarchical finite automata for behavior-description
Renát, Dušan ; Pergel, Martin (advisor) ; Holan, Tomáš (referee)
In the present work we introduce and study the hierarchical finite state machines as a model of artificial intelligence of autonomous agents in various virtual environments and systems. We define the concept of hierarchical finite state machine formally, analyze its computational power compared to common types of automata and point out the possibilities of increasing it. Then we list the usual methods of artificial intelligence simulation, tell apart the direct and indirect behavioral pattern description and present advantages of hierarchical finite state machines as a tool for the direct form. We propose a library interpreting these automata, created as a part of this work. By demonstrating its usage for controlling an example robot within the Robocode environment, we show that they are generic and viable solution for this kind of settings.
|
|
|
Multi-Dimensional Languages and Their Automata
Dibďák, Lukáš ; Martiško, Jakub (referee) ; Meduna, Alexandr (advisor)
The Bachelor's Thesis introduces the theory of formal languages and finite automata. It describes generalisation of one-dimensional theory into two dimensions. It introduces basic types of two-dimensional automata, especially on-line tessellation automata. This paper offers algorithms for the process of determinization of on-line tessellation automata. One of the algorithms is used in enclosed application.
|
|
|
Development of generation of Content Adressable Delayed DFA from Set of Regular Expression
Hammer, Jan ; Dvořák, Milan (referee) ; Kaštil, Jan (advisor)
This work deals with contruction of enhanced types of finite automata from sets of regular expressions. The main focus is on enhancement called CD2FA - Content Addressed Delayed Input DFA, which is designed to be used for deep packet inspection throughout the net, in order to lower memory requirements and retain the throughput. Automata constructed in this manner are used to get memory requirement statistics which show that CD2FAs are about ten times more compact then original DFAs. Then some enhancements dealing with the process of CD2FA construction are presented, particularly enhancement of preparation of state addressing by perfect hashing.
|
|
|
Intrusion Detection in Computer Network
Hank, Andrej ; Martínek, Tomáš (referee) ; Kořenek, Jan (advisor)
Continuous spreading and growing bandwidth of computer networks brings many security threats. Intrusion Detection System (IDS) is a mean to provide network security. Software IDS aplications gain only low throughput and that is why hardware accelerators are under heavy development. Probe Traffic Scanner is a hardware accelerator developed in Liberouter project with use of FPGA technology. Main core of acceleration is searching packet payload for simple suspicious strings. Regular expressions provide complex way of describing strings. This bachelor thesis adds feature of searching according to Perl Compatible Regular Expressions (PCRE) to Traffic Scanner Probe by implemented transformer. In addition design and implementation of control software allowing users to use functions provided by the Probe have been created. Conception of intrusion detection in network utilizing Traffic Scanner is outlined so as possibilities of cooperation with other security devices.
|
|
|
Simulation of Entities Collective Behavior in Virtual World
Vymazal, Tomáš ; Žák, Pavel (referee) ; Láník, Aleš (advisor)
Theme of this work is to evaluate and compare aviable paradigms for entity control in virtual worlds, and to implement one of these paradigms in application. Dynamic finite state machine upgraded using genetic algorithms has been chosen. This paradigm should make agent's behavior better and adapt agent to required state: i.e. make agent harvest resources in virtual world. Output of this work is application for running evolution and application for 3D view of agent's behavior.
|
guest ::
