67 %
33 %
Information about bk1

Published on January 16, 2008

Author: Rachele

Source: authorstream.com

Automatic Structures:  Automatic Structures Bakhadyr Khoussainov Computer Science Department The University of Auckland, New Zealand Plan:  Plan Lecture 1: 1. Motivation. 2. Finite Automata. Examples. 3. Building Automata. 4. Automatic Structures. Definition. 5. Examples. 6. Decidability Theorems I and II. 7. Definability Theorems. Plan:  Plan Lecture 2: 1. Automatic Boolean Algebras. 2. Automatic Linear Orders and Ranks. 3. Automatic Trees and Ranks. 4. Automatic Versions of Konig’s Lemma. 5. Definability and Intrinsic Regularity: a) Decidability Theorem III. b) Example: Intrinsic Regularity in (, S). Plan:  Plan Lecture 3: 1. Fraisse Limits and Their Automaticity: a. Random Graphs. b. Universal Partial Order. 2. The Isomorphism Problem for Automatic Structures is Σ11-complete. 3. Conclusion: What is Next? Motivation:  Motivation Refinement of the theory of computable structures A part of feasible mathematics Generalization of the theory of finite models A natural generalization of automata theory Automatic groups Infinite state systems. Roots go back to the late 50s and the 60s to early developments of automata theory by Buchi, Elgot, Eilenberg, Kleene, Rabin, Sheperdson. Finite Automata:  Finite Automata Fix an alphabet Σ. An automaton consists of: A finite set S of states. A subset I of S. States in I are initial states. A transition diagram Δ: SxΣ → P(S) A subset F of S. States in F are called final states. Automata can be represented as directed labeled graphs. Finite Automata:  Finite Automata Let w =a0 ….an be a word. The word is accepted by the automaton if there exists an accepting run of the automaton on the word. L(A)={w | w is accepted by A} Language L is FA recognizable if L=L(A) for some automaton A. Examples and Some Results:  Examples and Some Results {0w1 | w is a word}. {u101v | u,v are words}. {u0a1…an | each ai is 0 or 1, u is a word}. {w101 | w does not contain 101}. {w | the length of w is a multiple of 3}. Keene’s theorem. The star height hierarchy. NFA and DFA are equivalent (a few words). Building Automata:  Building Automata Let L1 and L2 be FA recognizable. Then the following languages are FA recognizable: The union of L1 and L2. The intersection of L1 and L2. The complement of L1. Building Automata:  Building Automata Projection Operation: Let Σ= Σ1x Σ2 be an alphabet. Let L be a language over Σ. Pr1(L)={w | u ((w,u) belongs to L) } If L is regular then so is Pr1(L). Regular Relations:  Regular Relations Consider a binary relation R on the set Σ*. Thus, R Σ* x Σ*. We want to define what it means that R is FA recognizable. There are several ways to define FA recognizable relations. There are research schools that study questions of this type. We follow Buchi’s original definition published in1960. Regular Relations:  We define the convolution of R. Take words u and v; Say, u=11001,v=1010100110. Write them one below the other: 11001 1010100110 and form the word c(u,v): Regular Relations Regular Relations:  Regular Relations c(u,v) is called the convolution of (u,v). Consider c(R)={c(u,v) | (u,v) belongs to R}. Note, c(R) is a language over new finite alphabet. Definition (Buchi and Elgot, 1960,1961). The relation R is FA recognizable (equivalently, regular) if its convolution c(R) is FA recognizable. Structures:  Structures A structure is a tuple (A; P0, P1,…,Pn, F0, F1…,Fm), where each P is a predicate symbol, and each F is a functional symbol. Assumptions: a) A is a countable set. b) Consider relational structures in which each function F is replaced by its graph. Structures:  Structures Examples: a) Graphs (V; E). b) Partial orders (P; ). c) Linear orders (L; ). d) Trees (T; ). e) Groups (G; +). f) Boolean algebras (B; , ∩, /, 0,1). g) Rings (R; +, x, 0,1). Definition: Automatic Structure (Hodgson 1976, Khoussainov and Nerode 1994):  Definition: Automatic Structure (Hodgson 1976, Khoussainov and Nerode 1994) A structure A=(A, P0, P1,…,Pn) is automatic if The domain A is a FA recognizable language, and each predicate Pi is a FA recognizable language. Definition: Automatic Structure:  Definition: Automatic Structure To describe an automatic structure one needs to explicitly specify: The alphabet. A finite automaton that recognizes the domain of the structure. Finite automata recognizing all the predicates of the structure. Examples::  Examples: The successor structure ({1}*; S), where S(w)=w1 The 2 successors structure ({0,1}*; L, R), where L(w)=w0 and R(w)=w1. The linear order ({1}*; <), where w<u iff the length of w is less than that of u. The binary tree ({0,1}*; prefix), where x prefix y iff x is a prefix of y. Examples:  Examples 5. The word structure ({0,1}*; L, R, <pref, EqL), where EqL(x,y) iff |x|=|y|. 6. The structure (N; +), where numbers are represented as binary words with least significant digits written from left to right and rightmost digit not being 0. Examples:  Examples 7. The Presburger arithmetic (N; S, +, ), where numbers are represented in binary. 8. Arithmetic with weak division (N; S, +, , |2 ), where x |2 y iff x is a power of two and y is a multiple of x. Examples:  Examples 9. Let T be a Turing machine. Consider the graph (Conf(T), E), where Conf(T) is the space of all configurations of T, and E(x,y) if there is a one-step transition from configuration x into y via T. 10. The structure ({0,1}*1; lex ). This is a dense linearly ordered set. Decidability Theorem I (Hodgson 1976, Khoussainov and Nerode, 1994):  Decidability Theorem I (Hodgson 1976, Khoussainov and Nerode, 1994) Let A be an automatic structure. There exists an algorithm that, given a FO formula Φ(x1,…,xn), builds an automaton that recognizes the set {(a1,…,an) | A satisfies Φ(a1,…,an)}. Proof. By induction on the length of the formula Φ. The disjunction corresponds to the union, negation to the complementation, and  to projection operations. Corollaries:  Corollaries The first order theory, that is, the set of all first order sentences true in any given automatic structure is decidable. 2. The first order theory of Presburger arithmetic (N; S, 0, <, +) is decidable. Decidability Theorem II (Gradel and Blumensath, in LICS 2000):  Decidability Theorem II (Gradel and Blumensath, in LICS 2000) Let A be an automatic structure. There exists an algorithm that, given a formula Φ(x1,…,xn) in FO+ω , builds an automaton for the set: {(a1,…,an) | A satisfies Φ(x1,…,xn)}. Proof. Extend A to (A, <llex ). Now, any formula ω x Φ(x,z) is equivalent to y x (y<llexx & Φ(x,z) ). Corollaries::  Corollaries: 4. Let (T; <) be an automatic finitely branching infinite tree. Then it has a regular infinite path. Proof. Consider (T;<, <llex ). Here is a FO+ ω definition of an infinite path. Good(x) if any y below or equal to x is the <llex-first immediate successor of its parent such that there are infinitely many z above y. Comment::  Comment: Consider: e1(n)=2n, et(n)=the tower of 2s of length t to the power of n. The  quantifier brings non-determinism. The negation which follows  brings exponential blow up in the number of states. So, the t blocks of the negation symbol followed by  in a formula yields an automaton with et(n) number of states. Comment::  Comment: If A is automatic then the time complexity of the algorithm deciding the theory of A is non-elementary. Theorem (Blumensath, Gradel, LICS 2000). The time complexity of the first order theory of (N; S, +, <, |2 ) is non-elementary. M. Lohrey (2003): The theory of any automatic finitely branching graph is double exponential. F. Fleadtke (2003): The known lower bound for Presburger arithmetic is matched via automata. Definition: Automatic Presentations (Khoussainov and Nerode 1994):  Definition: Automatic Presentations (Khoussainov and Nerode 1994) Let A be a structure. An automatic presentation of A, or equivalently, automatic copy of A, is any automatic structure isomorphic to A. If A has an automatic presentation then A is called FA presentable. Automata Presentable Structures: Examples:  Automata Presentable Structures: Examples 1. The group (Z; +). More generally, finitely generated Abelian groups. 2. Boolean Algebras Bi 3. Linear Orders: Σ(η+2n) 4. Graphs. 5. Equivalence Structures. Definability Theorem I (Buchi 1960, Elgot 1961, Eilenberg, Elgot and Sheperdson 1969, Bruere et al. 1994, Blumensath and Gradel 1999):  Definability Theorem I (Buchi 1960, Elgot 1961, Eilenberg, Elgot and Sheperdson 1969, Bruere et al. 1994, Blumensath and Gradel 1999) A structure A has an automatic presentation iff A is isomorphic to a structure definable in ({0,1}*; L, R, prefix, EqL). Proof. One direction is clear. The other direction: Let A be an automatic. Fact: We can assume that the alphabet is {0,1}. Definability Theorem I (Proof)::  Definability Theorem I (Proof): It suffices to show that any regular relation R over {0,1} is definable. Say, for simplicity, R is unary. Assume M accepts R: 1. {1,….,m} are the states of M; 1 is the initial state 2.  is the transition table. 3. F is the set of all accepting states. Definability Theorem I (Proof):  Definability Theorem I (Proof) Want to build Φ(x) such that for all w in {0,1}* the word w is in R iff Φ(w) is true. The formula needs to say the following: There exist words s1,…., sm such that the word si simulates state i. The word si is a binary sequence such that the jth component is 1 iff the jth component of the run on x is i. The run should be accepting. Definability Theorem I (Proof)::  Definability Theorem I (Proof): More formally, Φ(x) says: s1s2….sm: 1. The first digit of s1 is 1. 2. For any position p only one of words si has 1. 3. If pth digit of si is 1 and the pth digit of x is σ then (p+1)th digit of sj is 1, where (i, σ)=j. 4. If the (|x|+1)th digit of sk is 1 then k is in F. All these can be expressed in the FO logic. Definability Theorem II (Gradel & Blumeansath, 2000):  Definability Theorem II (Gradel & Blumeansath, 2000) The following are equivalent: 1. A is automatic over binary alphabet. 2. A is definable in ({0,1}*; L, R, prefix, EqL). 3. A is definable in (N; S, +, , |2 ). Definability Theorem III (Nabebin 1976, Blumensath 1999):  Definability Theorem III (Nabebin 1976, Blumensath 1999) A structure A has an automatic presentation over a unary alphabet if and only if it is isomorphic to a structure definable in (; , mod(2), mod(3), mod(4),…)

Add a comment

Related presentations

Related pages

Aktuelles - Kaufmännische Schulen Offenburg

Wir arbeiten gemeinsam an dem Ziel, Jugendliche und junge Erwachsene durch Ausbildung und Erziehung bestmöglich auf ihre berufliche und private Zukunft ...
Read more

Berufskolleg – Wikipedia

Kaufmännisches Berufskolleg Fremdsprachen. Das Kaufmännische Berufskolleg Fremdsprachen ist eine zweijährige Schule, die eine kaufmännisch ...
Read more

Was ist BK1 könnt ihr mir es bitte erklären? (Wissen)

Was ist BK1 ????? bitte erklären. ich habe es auch geh googelt aber dah kommen so komische seiten.
Read more

Berufskolleg 1 - Walter-Eucken-Schule Karlsruhe

Das Kaufmännische Berufskolleg 1 (BK1) vermittelt die für die kaufmännischen Tätigkeiten in Wirtschaft und Verwaltung erforderlichen Grundkenntnisse ...
Read more

Anmeldung - Kaufmännische Schulen Offenburg

BK1. keine Abschlussprüfung; Vorstufe zu BK2; Dauer: 1 Jahr; Allgemeinbildung Wirtschaft; Zur Anmeldung Berufskolleg 2. BK2. setzt BK1 voraus; mit ...
Read more

Berufskolleg - wss.tue.bw.schule.de

Info-Flyer BK1 (ca. 15 MB) Aufnahmebedingungen (Stand: Dezember 2015) Aufnahmeantrag; BKFH - einjährig ...
Read more

CTS :: Schularten :: BK1 :: Abschluss - carl-theodor-schule.de

Berufskolleg I (einjährig) - Abschluss. Wer die Ausbildung erfolgreich abgeschlossen hat, erhält ein Abschlusszeugnis. Für den erfolgreichen Abschluss ...
Read more

CTS :: Schularten :: BK1 :: Zugangsvoraussetzungen

Offizielle Website der kaufmännischen beruflichen Carl-Theodor-Schule in Schwetzingen.
Read more


Nightclub BK1 is a new redesigned venue located at the central trainstation in Kaldenkirchen, Germany.
Read more

Rockwell B-1 – Wikipedia

Die Rockwell B-1 Lancer, seit der Übernahme von Rockwell International durch Boeing auch Boeing B-1, ist ein überschallschneller, strategischer ...
Read more