Martin Huschenbett

The Model-Theoretic Complexity of Automatic Linear Orders

Autor: Martin Huschenbett

ISBN: 978-3-86360-127-0

Seitenzahl: 228

Erscheinungsdatum: 08.01.2016


Print on Demand – bis zu 10 Werktage Lieferzeit!

16,50 € *

Produktinformationen "The Model-Theoretic Complexity of Automatic Linear Orders"

Automatic structures are—possibly infinite—structures which are finitely presentable by means of finite automata on strings or trees. Largely motivated by the fact that their first-order theories are uniformly decidable, automatic structures gained a lot of attention in the "logic in computer science" community during the last fifteen years. This thesis studies the model-theoretic complexity of automatic linear orders in terms of two complexity measures: the finite-condensation rank and the Ramsey degree. The former is an ordinal which indicates how far a linear order is away from being dense. The corresponding main results establish optimal upper bounds on this rank with respect to several notions of automaticity. The Ramsey degree measures the model-theoretic complexity of well-orders by means of the partition relations studied in combinatorial set theory. This concept is investigated in a purely set-theoretic setting as well as in the context of automatic structures.

Weiterführende Links zu "The Model-Theoretic Complexity of Automatic Linear Orders"

Bücher in diesem Shop von Martin Huschenbett

Kundenbewertungen für "The Model-Theoretic Complexity of Automatic Linear Orders"

Bewertungen werden nach Überprüfung freigeschaltet.

Bewertung schreiben


Die mit einem * markierten Felder sind Pflichtfelder.