Abstract
We establish the eventual periodicity of the spectrum of any monadic second-order formula where (i) all relation symbols, except equality, are unary, and (ii) there is only one function symbol and that symbol is unary.
Logic in Computer Science, Symposium on
Like what you’re reading?
Already a member?
Related Articles
- Monadic second-order logic and hypergraph orientation
Proceedings of 8th Annual IEEE Symposium on Logic in Computer Science - Monadic Second-Order Logic and Bisimulation Invariance for Coalgebras
2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - Graph connectivity and monadic NP
Proceedings 35th Annual Symposium on Foundations of Computer Science - First-Order and Monadic Second-Order Model-Checking on Ordered Structures
Logic in Computer Science, Symposium on - Lower Bounds for the Complexity of Monadic Second-Order Logic
Logic in Computer Science, Symposium on - On the decidability of linear Z-temporal logic and the monadic second order theory of the integers
1992 Fourth International Conference on Computing and Information - The order types of termination orderings on monadic terms, strings and multisets
Proceedings of 8th Annual IEEE Symposium on Logic in Computer Science - Quantitative Monadic Second-Order Logic
Logic in Computer Science, Symposium on - Quantifying Over Trees in Monadic Second-Order Logic
2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) - Axiomatizations and Computability of Weighted Monadic Second-Order Logic
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)