Eventual periodicity and ``one-dimensional'' queries
type: Item
instance of: scholarly article
title: Eventual periodicity and ``one-dimensional'' queries
zbMATH Open document ID: 0768.03002
published in: Notre Dame Journal of Formal Logic
publication date: 1993-02-22T00:00:00Z
review text: A generalization of the (finite version of the) Büchi-Ladner representation theorem for monadic second order Boolean queries on chainlike graphs is presented. A careful application of the monotonicity of one-dimensional least fixed point inductions results in the discovery that these inductions express fewer Boolean queries than even the monadic \(\Delta^ 1_ 1\) formulas.
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 03D05
zbMATH DE Number: 120392
zbMATH Keywords: monadic second order logic
zbMATH Keywords: monadic least fixed point logic
zbMATH Keywords: monadic second order queries
zbMATH Keywords: multigraph
zbMATH Keywords: pebble game
zbMATH Keywords: chainlike graphs
author: Gregory Loren McColm
reviewed by: Gregory Loren McColm
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1093636105
OpenAlex ID: W2056059644
DOI: 10.1305/NDJFL/1093636105
description: scientific article; zbMATH DE number 120392