Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAutomatic Structures: Richness and Limitations
110
0
0.0
(
0
)
Added by
Frank Stephan
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by synchronised automata. Our first topic concerns characterising classes of automatic structures. We supply a characterisation of the automatic Boolean algebras, and it is proven that the free Abelian group of infinite rank, as well as certain Fraisse limits, do not have automatic presentations. In particular, the countably infinite random graph and the random partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. Our second topic is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is Sigma_1^1-complete.
rate research
Read More
We consider $omega^n$-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length $omega^n$ for some integer $ngeq 1$. We show that all these structures are $omega$-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for $omega^2$-automatic (resp. $omega^n$-automatic for $n>2$) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for $omega^n$-automatic boolean algebras, $n > 1$, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a $Sigma_2^1$-set nor a $Pi_2^1$-set. We obtain that there exist infinitely many $omega^n$-automatic, hence also $omega$-tree-automatic, atomless boolean algebras $B_n$, $ngeq 1$, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [FT10].
An $omega$-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for $omega$-tree-automatic structures. We prove first that the isomorphism relation for $omega$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is not determined by the axiomatic system ZFC. Then we prove that the isomorphism problem for $omega$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is neither a $Sigma_2^1$-set nor a $Pi_2^1$-set.
Affine $lambda$-terms are $lambda$-terms in which each bound variable occurs at most once and linear $lambda$-terms are $lambda$-terms in which each bound variables occurs once. and only once. In this paper we count the number of closed affine $lambda$-terms of size $n$, closed linear $lambda$-terms of size $n$, affine $beta$-normal forms of size $n$ and linear $beta$-normal forms of ise $n$, for different ways of measuring the size of $lambda$-terms. From these formulas, we show how we can derive programs for generating all the terms of size $n$ for each class. For this we use a specific data structure, which are contexts taking into account all the holes at levels of abstractions.
We study the (hereditary) discrepancy of definable set systems, which is a natural measure for their inherent complexity and approximability. We establish a strong connection between the hereditary discrepancy and quantifier elimination over signatures with only unary relation and function symbols. We prove that set systems definable in theories (over such signatures) with quantifier elimination have constant hereditary discrepancy. We derive that set systems definable in bounded expansion classes, which are very general classes of uniformly sparse graphs, have bounded hereditary discrepancy. We also derive that nowhere dense classes, which are more general than bounded expansion classes, in general do not admit quantifier elimination over a signature extended by an arbitrary number of unary function symbols. We show that the set systems on a ground set $U$ definable on a monotone nowhere dense class of graphs $mathscr C$ have hereditary discrepancy at most $|U|^{c}$ (for some~$c<1/2$) and that, on the contrary, for every monotone somewhere dense class $mathscr C$ and for every positive integer $d$ there is a set system of $d$-tuples definable in $mathscr C$ with discrepancy $Omega(|U|^{1/2})$. We further prove that if $mathscr C$ is a class of graphs with bounded expansion and $phi(bar x;bar y)$ is a first-order formula, then we can compute in polynomial time, for an input graph $Ginmathscr C$, a mapping $chi:V(G)^{|bar x|}rightarrow{-1,1}$ witnessing the boundedness of the discrepancy of the set-system defined by~$phi$, an $varepsilon$-net of size $mathcal{O}(1/varepsilon)$, and an $varepsilon$-approximation of size $mathcal{O}(1/varepsilon)$.
We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $omega^{omega^omega}$. Then we show that the injectively $omega^n$-automatic ordinals, where $n>0$ is an integer, are the ordinals smaller than $omega^{omega^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11] the subclasses of finite word $omega^n$-automatic ordinals. As a by-product we obtain that the hierarchy of injectively $omega^n$-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
