{"id":{"repo_id":"helsinki","oai_identifier":"oai:helda.helsinki.fi:10138/315510"},"canonical_url":"https://search.dev.ndltd.org/etd/helsinki/oai:helda.helsinki.fi:10138/315510","repository":{"repo_id":"helsinki","name":"University of Helsinki","base_url":"https://helda.helsinki.fi/server/oai/request"},"display":{"title":"Transitive Closure Logic and Multihead Automata with Nested Pebbles","abstract":"Several extensions of first-order logic are studied in descriptive complexity theory. These extensions include transitive closure logic and deterministic transitive closure logic, which extend first-order logic with transitive closure operators. It is known that deterministic transitive closure logic captures the complexity class of the languages that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities of transitive closure operators appearing in formulas are restricted to a nonzero natural number k. The expressivity of these fragments can be studied in terms of multihead finite automata. The type of automaton that we consider in this thesis is a two-way multihead automaton with nested pebbles. We look at the expressive power of multihead automata and the k-ary fragments of transitive closure logics in the class of finite structures called word models. We show that deterministic twoway k-head automata with nested pebbles have the same expressive power as first-order logic with k-ary deterministic transitive closure. For a corresponding result in the case of nondeterministic automata, we restrict to the positive fragment of k-ary transitive closure logic. The two theorems and their proofs are based on the article ’Automata with nested pebbles capture first-order logic with transitive closure’ by Joost Engelfriet and Hendrik Jan Hoogeboom. In the article, the results are proved in the case of trees. Since word models can be viewed as a special type of trees, the theorems considered in this thesis are a special case of a more general result.","abstract_html":"Several extensions of first-order logic are studied in descriptive complexity theory. These extensions include transitive closure logic and deterministic transitive closure logic, which extend first-order logic with transitive closure operators. It is known that deterministic transitive closure logic captures the complexity class of the languages that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities of transitive closure operators appearing in formulas are restricted to a nonzero natural number k. The expressivity of these fragments can be studied in terms of multihead finite automata. The type of automaton that we consider in this thesis is a two-way multihead automaton with nested pebbles. We look at the expressive power of multihead automata and the k-ary fragments of transitive closure logics in the class of finite structures called word models. We show that deterministic twoway k-head automata with nested pebbles have the same expressive power as first-order logic with k-ary deterministic transitive closure. For a corresponding result in the case of nondeterministic automata, we restrict to the positive fragment of k-ary transitive closure logic. The two theorems and their proofs are based on the article ’Automata with nested pebbles capture first-order logic with transitive closure’ by Joost Engelfriet and Hendrik Jan Hoogeboom. In the article, the results are proved in the case of trees. Since word models can be viewed as a special type of trees, the theorems considered in this thesis are a special case of a more general result.","abstract_has_math":false,"creators":["Hirvonen, Minna"],"institution":"Helsingin yliopisto","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta","University of Helsinki, Faculty of Science","Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020","date_published":"2020","updated_at":"2026-07-27T19:56:19Z","subjects":["First-order logic","transitive closure","multihead automata","pebbles","word models"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["URN:NBN:fi:hulib-202005272339"],"render_values":[{"text":"URN:NBN:fi:hulib-202005272339","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10138/315510","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta","University of Helsinki, Faculty of Science","Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten"]},{"key":"dc:creator","label":"Author","values":["Hirvonen, Minna"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2020"]},{"key":"dc:publisher","label":"Institution","values":["Helsingin yliopisto","University of Helsinki","Helsingfors universitet"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["First-order logic","transitive closure","multihead automata","pebbles","word models"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["URN:NBN:fi:hulib-202005272339","http://hdl.handle.net/10138/315510"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Several extensions of first-order logic are studied in descriptive complexity theory. These extensions include transitive closure logic and deterministic transitive closure logic, which extend first-order logic with transitive closure operators. It is known that deterministic transitive closure logic captures the complexity class of the languages that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities of transitive closure operators appearing in formulas are restricted to a nonzero natural number k. The expressivity of these fragments can be studied in terms of multihead finite automata. The type of automaton that we consider in this thesis is a two-way multihead automaton with nested pebbles. We look at the expressive power of multihead automata and the k-ary fragments of transitive closure logics in the class of finite structures called word models. We show that deterministic twoway k-head automata with nested pebbles have the same expressive power as first-order logic with k-ary deterministic transitive closure. For a corresponding result in the case of nondeterministic automata, we restrict to the positive fragment of k-ary transitive closure logic. The two theorems and their proofs are based on the article ’Automata with nested pebbles capture first-order logic with transitive closure’ by Joost Engelfriet and Hendrik Jan Hoogeboom. In the article, the results are proved in the case of trees. Since word models can be viewed as a special type of trees, the theorems considered in this thesis are a special case of a more general result."]},{"key":"dc:title","label":"Title","values":["Transitive Closure Logic and Multihead Automata with Nested Pebbles"]}]}],"canonical_facts":{"dc:contributor":["Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta","University of Helsinki, Faculty of Science","Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten"],"dc:creator":["Hirvonen, Minna"],"dc:date.issued":["2020"],"dc:description.abstract":["Several extensions of first-order logic are studied in descriptive complexity theory. These extensions include transitive closure logic and deterministic transitive closure logic, which extend first-order logic with transitive closure operators. It is known that deterministic transitive closure logic captures the complexity class of the languages that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities of transitive closure operators appearing in formulas are restricted to a nonzero natural number k. The expressivity of these fragments can be studied in terms of multihead finite automata. The type of automaton that we consider in this thesis is a two-way multihead automaton with nested pebbles. We look at the expressive power of multihead automata and the k-ary fragments of transitive closure logics in the class of finite structures called word models. We show that deterministic twoway k-head automata with nested pebbles have the same expressive power as first-order logic with k-ary deterministic transitive closure. For a corresponding result in the case of nondeterministic automata, we restrict to the positive fragment of k-ary transitive closure logic. The two theorems and their proofs are based on the article ’Automata with nested pebbles capture first-order logic with transitive closure’ by Joost Engelfriet and Hendrik Jan Hoogeboom. In the article, the results are proved in the case of trees. Since word models can be viewed as a special type of trees, the theorems considered in this thesis are a special case of a more general result."],"dc:identifier.uri":["URN:NBN:fi:hulib-202005272339","http://hdl.handle.net/10138/315510"],"dc:language.iso":["eng"],"dc:publisher":["Helsingin yliopisto","University of Helsinki","Helsingfors universitet"],"dc:subject":["First-order logic","transitive closure","multihead automata","pebbles","word models"],"dc:title":["Transitive Closure Logic and Multihead Automata with Nested Pebbles"]},"updated_at":"2026-07-27T19:56:19Z"}