Original title: Alternativní koncept dvousměrných konečných automatů
Translated title: Two-Way Finite Automata: an Alternative Concept
Authors: Nejedlý, Dominik ; Klembara, Radovan (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2025
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Tato práce zavádí a studuje alternativní koncept dvousměrných konečných automatů, který je označován jako vstup vymazávající dvousměrné konečné automaty. Podobně jako původní model mohou i tyto automaty posunovat čtecí hlavu po vstupní pásce libovolně doleva či doprava, avšak každý přečtený symbol ze vstupní pásky vymazávají. Práce demonstruje, že tyto automaty definují přesně třídu lineárních jazyků a jsou tedy silnější než jejich původní verze. Dále zavádí různá omezení kladená na tyto automaty a způsob, kterým pracují, a zkoumá vliv těchto omezení na jejich přijímací sílu. Zabývá se především vzájemnými vztahy mezi jazykovými rodinami, které z těchto omezení vyplývají, a ukazuje, že některá z nich snižují sílu těchto automatů na úroveň vyrovnaných lineárních gramatik nebo dokonce běžných konečných automatů. This thesis introduces and studies an alternative concept of two-way finite automata referred to as input-erasing two-way finite automata. Like the original model, these new automata can also move their read heads freely left or right on their input tapes. However, each time they read a symbol, they also erase it from their tapes. The thesis demonstrates that these automata define precisely the family of linear languages and are thus strictly stronger than their original versions. Furthermore, it introduces a variety of restrictions placed upon these automata and the way they work and investigates the effect of these restrictions on their accepting power. In particular, it explores mutual relations between the language families resulting from these restrictions and shows that some of them reduce the power of these automata to that of even linear grammars or even ordinary finite automata.
Keywords: levé a pravé přechody; lineární jazyky; střídavý výpočet; vstup vymazávající dvousměrné konečné automaty; vyrovnané lineární jazyky; vyrovnaný výpočet; alternating computation; even computation; even linear languages; input-erasing two-way finite automata; left and right moves; linear languages

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/255102

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


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