On optimal representatives of finite coloured linear orders

DOI10.1007/S11083-018-9458-3MaRDI QIDQ1732807zbMATH OpenOpenAlexWikidataFDO

Authors Feresiano Mwesigye, John K. Truss

Publication date 25 March 2019

Published in Order (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1705.04632

zbMATH Keywords

classificationoptimalitycoloured linear orderEhrenfeucht-Fraïssé game

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Total orders (06A05)

Abstract: Two structures A and B are n-equivalent if player II has a winning strategy in the n-move Ehrenfeucht-Fraisse game on A and B. We extend earlier results about n-equivalence for finite coloured linear orders, describing an algorithm for reducing to canonical form under 2-equivalence, and concentrating on the cases of 2 and 3 moves.

Recommendations

• Ehrenfeucht-Fraïssé games on ordinals
• Classification of finite coloured linear orderings
• Ehrenfeucht-Fraïssé games on a class of scattered linear orders
• On quantifier-rank equivalence between linear orders
• On complexity of Ehrenfeucht-Fraïssé games

Cites work

• Classification of finite coloured linear orderings
• Ehrenfeucht-Fraïssé games on ordinals

Cited in

(5)

• On quantifier-rank equivalence between linear orders
• Ehrenfeucht-Fraïssé games on ordinals
• Ehrenfeucht-Fraïssé games on a class of scattered linear orders
• Classification of finite coloured linear orderings
• Coloring linear orders with Rado's partial order

This page was built for publication: On optimal representatives of finite coloured linear orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1732807)