On decidability of list structures

DOI10.1134/S0037446619030029zbMath1481.03029OpenAlexW2949935791WikidataQ127701830 ScholiaQ127701830MaRDI QIDQ2332060

S. A. Aleksandrova, Nikolay Bazhenov

Publication date: 1 November 2019

Published in: Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0037446619030029

zbMATH Keywords

automatic structuredecidable structurelist structurelinear listtree automatic structure

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Theory of numerations, effectively presented structures (03D45)

Related Items (1)

The expressiveness of looping terms in the semantic programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures
• Axiomatic data type specifications: A first order theory of linear lists
• Computable structures and the hyperarithmetical hierarchy
• Monadic second-order logic on tree-like structures
• Conditional terms in semantic programming
• Recursive terms in semantic programming
• Automaticity of ordinals and of homogeneous graphs
• The uniformization problem for \(\Sigma\)-predicates in a hereditarily finite list superstructure over the real exponential field
• Automatic structures and the theory of lists
• Three Lectures on Automatic Structures
• Weak Second‐Order Arithmetic and Finite Automata
• Automata Presenting Structures: A Survey of the Finite String Case
• Σ-programming
• STACS 2004
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Automatic presentations of structures

This page was built for publication: On decidability of list structures