{"id":{"repo_id":"freiburg-diss","oai_identifier":"oai:freidok.uni-freiburg.de:1457"},"canonical_url":"https://search.dev.ndltd.org/etd/freiburg-diss/oai:freidok.uni-freiburg.de:1457","repository":{"repo_id":"freiburg-diss","name":"University of Freiburg","base_url":"https://freidok.uni-freiburg.de/oai/oai2.php"},"display":{"title":"Model-checking problems, machines and parameterized complexity","abstract":"Parameterized complexity is a new approach to deal with classical
intractable problem. It is built on a novel notion of
tractability, i.e., fixed-parameter tractability, which
admits algorithms that have exponential running time, but
just in terms of parameter of the problem instance that
is expected to be small in the typical applications.
Significant progress has been made to identify those
classical intractable problems that have fixed-parameter
tractable algorithms. Meanwhile a great number of parameterized
intractable classes has been identified to classify problems that
seem fixed-parameter intractable,
which resembles the classical NP-completeness theory.
However almost all
those classes are defined as closures of kernel problems
under some type of reductions.
The main topic of our thesis is to provide natural machine
characterizations of all major parameterized classes. The starting
point is the class W[P], which we characterize as the languages
that are decidable by nondeterministic fixed-parameter
tractable algorithms of random access machines whose use of
nondeterminism is bounded in terms of the parameters. By
further tuning the nondeterminism that the random access machines can use,
say, allowing alternating, or restricting the access to
the guessed numbers, we obtain machine characterizations of
almost all important parameterized complexity classes.
We also investigate some structural issues
of parameterized complexity in the light of these
machine characterizations.
Our main technical tools are model-checking problems.
The parameterized classes we deal with are originally defined
via various satisfiability problems or halting problems
of Turing machines. However there are model-checking problems of
natural fragments of first-order logic complete for some
of the most important classes. And model-checking problems
are much more manageable than those hard combinatorics
required to deal with those classes when using the original
definitions. On the other hand parameterized complexity
has proved to be a more appropriate framework of analysing
the complexity of model-checking problems. We investigate model-checking
problems on structures with functions, while most previous
works study relational structures. Based on that we introduce
a new hierarchy of classes and prove some basic complete results
and give their machine characterizations.
Finally we also study the halting problems of Turing machines
in the context of parameterized complexity. It is previous known
that some natural halting problems are complete for some
parameterized classes. We give halting problems of other important
classes.","abstract_html":"Parameterized complexity is a new approach to deal with classical <br>intractable problem. It is built on a novel notion of <br>tractability, i.e., fixed-parameter tractability, which <br>admits algorithms that have exponential running time, but <br>just in terms of parameter of the problem instance that <br>is expected to be small in the typical applications. <br>Significant progress has been made to identify those <br>classical intractable problems that have fixed-parameter <br>tractable algorithms. Meanwhile a great number of parameterized <br>intractable classes has been identified to classify problems that <br>seem fixed-parameter intractable, <br>which resembles the classical NP-completeness theory. <br>However almost all <br>those classes are defined as closures of kernel problems <br>under some type of reductions. <br> <br>The main topic of our thesis is to provide natural machine <br>characterizations of all major parameterized classes. The starting <br>point is the class W[P], which we characterize as the languages <br>that are decidable by nondeterministic fixed-parameter <br>tractable algorithms of random access machines whose use of <br>nondeterminism is bounded in terms of the parameters. By <br>further tuning the nondeterminism that the random access machines can use, <br>say, allowing alternating, or restricting the access to <br>the guessed numbers, we obtain machine characterizations of <br>almost all important parameterized complexity classes. <br>We also investigate some structural issues <br>of parameterized complexity in the light of these <br>machine characterizations. <br> <br>Our main technical tools are model-checking problems. <br>The parameterized classes we deal with are originally defined <br>via various satisfiability problems or halting problems <br>of Turing machines. However there are model-checking problems of <br>natural fragments of first-order logic complete for some <br>of the most important classes. And model-checking problems <br>are much more manageable than those hard combinatorics <br>required to deal with those classes when using the original <br>definitions. On the other hand parameterized complexity <br>has proved to be a more appropriate framework of analysing <br>the complexity of model-checking problems. We investigate model-checking <br>problems on structures with functions, while most previous <br>works study relational structures. Based on that we introduce <br>a new hierarchy of classes and prove some basic complete results <br>and give their machine characterizations. <br> <br>Finally we also study the halting problems of Turing machines <br>in the context of parameterized complexity. It is previous known <br>that some natural halting problems are complete for some <br>parameterized classes. We give halting problems of other important <br>classes.","abstract_has_math":false,"creators":["Chen, Yijia"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Flum, Jörg"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T02:22:16Z","subjects":["Model-Checking","Machine","Parameterized Complexity"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://freidok.uni-freiburg.de/data/1457","outbound_label":"Repository record","outbound_source":"source_url"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Flum, Jörg"]},{"key":"dc:creator","label":"Author","values":["Chen, Yijia"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["DoctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Model-Checking","Machine","Parameterized Complexity"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Parameterized complexity is a new approach to deal with classical
intractable problem. It is built on a novel notion of
tractability, i.e., fixed-parameter tractability, which
admits algorithms that have exponential running time, but
just in terms of parameter of the problem instance that
is expected to be small in the typical applications.
Significant progress has been made to identify those
classical intractable problems that have fixed-parameter
tractable algorithms. Meanwhile a great number of parameterized
intractable classes has been identified to classify problems that
seem fixed-parameter intractable,
which resembles the classical NP-completeness theory.
However almost all
those classes are defined as closures of kernel problems
under some type of reductions.
The main topic of our thesis is to provide natural machine
characterizations of all major parameterized classes. The starting
point is the class W[P], which we characterize as the languages
that are decidable by nondeterministic fixed-parameter
tractable algorithms of random access machines whose use of
nondeterminism is bounded in terms of the parameters. By
further tuning the nondeterminism that the random access machines can use,
say, allowing alternating, or restricting the access to
the guessed numbers, we obtain machine characterizations of
almost all important parameterized complexity classes.
We also investigate some structural issues
of parameterized complexity in the light of these
machine characterizations.
Our main technical tools are model-checking problems.
The parameterized classes we deal with are originally defined
via various satisfiability problems or halting problems
of Turing machines. However there are model-checking problems of
natural fragments of first-order logic complete for some
of the most important classes. And model-checking problems
are much more manageable than those hard combinatorics
required to deal with those classes when using the original
definitions. On the other hand parameterized complexity
has proved to be a more appropriate framework of analysing
the complexity of model-checking problems. We investigate model-checking
problems on structures with functions, while most previous
works study relational structures. Based on that we introduce
a new hierarchy of classes and prove some basic complete results
and give their machine characterizations.
Finally we also study the halting problems of Turing machines
in the context of parameterized complexity. It is previous known
that some natural halting problems are complete for some
parameterized classes. We give halting problems of other important
classes.","Wir geben Maschinencharakterisierung von die parametrischer Komplexitätsklassen. Wir studieren auch die Halting-Probleme
im Kontext der parametrische Komplexitätstheorie."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Model-checking problems, machines and parameterized complexity","Model-Checking-Probleme, Maschinen und Parametrische Komplexitätstheorie"]}]}],"canonical_facts":{"dc:contributor":["Flum, Jörg"],"dc:creator":["Chen, Yijia"],"dc:description.abstract":["Parameterized complexity is a new approach to deal with classical
intractable problem. It is built on a novel notion of
tractability, i.e., fixed-parameter tractability, which
admits algorithms that have exponential running time, but
just in terms of parameter of the problem instance that
is expected to be small in the typical applications.
Significant progress has been made to identify those
classical intractable problems that have fixed-parameter
tractable algorithms. Meanwhile a great number of parameterized
intractable classes has been identified to classify problems that
seem fixed-parameter intractable,
which resembles the classical NP-completeness theory.
However almost all
those classes are defined as closures of kernel problems
under some type of reductions.
The main topic of our thesis is to provide natural machine
characterizations of all major parameterized classes. The starting
point is the class W[P], which we characterize as the languages
that are decidable by nondeterministic fixed-parameter
tractable algorithms of random access machines whose use of
nondeterminism is bounded in terms of the parameters. By
further tuning the nondeterminism that the random access machines can use,
say, allowing alternating, or restricting the access to
the guessed numbers, we obtain machine characterizations of
almost all important parameterized complexity classes.
We also investigate some structural issues
of parameterized complexity in the light of these
machine characterizations.
Our main technical tools are model-checking problems.
The parameterized classes we deal with are originally defined
via various satisfiability problems or halting problems
of Turing machines. However there are model-checking problems of
natural fragments of first-order logic complete for some
of the most important classes. And model-checking problems
are much more manageable than those hard combinatorics
required to deal with those classes when using the original
definitions. On the other hand parameterized complexity
has proved to be a more appropriate framework of analysing
the complexity of model-checking problems. We investigate model-checking
problems on structures with functions, while most previous
works study relational structures. Based on that we introduce
a new hierarchy of classes and prove some basic complete results
and give their machine characterizations.
Finally we also study the halting problems of Turing machines
in the context of parameterized complexity. It is previous known
that some natural halting problems are complete for some
parameterized classes. We give halting problems of other important
classes.","Wir geben Maschinencharakterisierung von die parametrischer Komplexitätsklassen. Wir studieren auch die Halting-Probleme
im Kontext der parametrische Komplexitätstheorie."],"dc:format.medium":["application/pdf"],"dc:subject":["Model-Checking","Machine","Parameterized Complexity"],"dc:title":["Model-checking problems, machines and parameterized complexity","Model-Checking-Probleme, Maschinen und Parametrische Komplexitätstheorie"],"dc:type":["DoctoralThesis"]},"updated_at":"2026-07-24T02:22:16Z"}