Unary FA-presentable binary relations: transitivity and classification results
From MaRDI portal
Publication:6240010
arXiv1303.0214MaRDI QIDQ6240010FDOQ6240010
Publication date: 1 March 2013
Abstract: Automatic presentations, also called FA-presentations, were introduced to extend finite model theory to infinite structures whilst retaining the solubility of fundamental decision problems. A particular focus of research has been the classification of those structures of some species that admit FA-presentations. Whilst some successes have been obtained, this appears to be a difficult problem in general. A restricted problem, also of significant interest, is to ask this question for unary FA-presentations: that is, FA-presentations over a one-letter alphabet. This paper studies unary FA-presentable binary relations. It is proven that transitive closure of a unary FA-presentable binary relation is itself unary FA-presentable. Characterizations are then given of unary FA-presentable binary relations, quasi-orders, partial orders, tournaments, directed trees and forests, undirected trees and forests, and the orbit structures of unary FA-presentable partial and complete mappings, injections, surjections, and bijections.
Formal languages and automata (68Q45) Trees (05C05) Combinatorics of partially ordered sets (06A07) Theory of numerations, effectively presented structures (03D45)
This page was built for publication: Unary FA-presentable binary relations: transitivity and classification results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6240010)
