Exact complexity bounds for ordinal addition

DOI10.1016/0304-3975(95)00221-9zbMATH Open0872.68118OpenAlexW2048865589MaRDI QIDQ671516FDOQ671516

Authors: Françoise Maurin 

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00221-9

Recommendations

• scientific article; zbMATH DE number 2087209
• Tree Automata Make Ordinal Theory Easy
• DETERMINISTIC AUTOMATA AND THE MONADIC THEORY OF ORDINALS < ω2
• Complexity and (un)decidability of fragments of \(\langle \omega^{\omega^{\lambda}};\times\rangle\)
• Ehrenfeucht games and ordinal addition

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• scientific article; zbMATH DE number 3880651 (Why is no real title available?)
• scientific article; zbMATH DE number 3652325 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3510287 (Why is no real title available?)
• scientific article; zbMATH DE number 3627183 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3329919 (Why is no real title available?)
• A Decision Procedure for the First Order Theory of Real Addition with Order
• A uniform method for proving lower bounds on the computational complexity of logical theories
• The complexity of logical theories
• The first order properties of products of algebraic systems
• The theory of integer multiplication with order restricted to primes is decidable
• Weak Second‐Order Arithmetic and Finite Automata

Cited In (4)

• Complexity and (un)decidability of fragments of \(\langle \omega^{\omega^{\lambda}};\times\rangle\)
• Tree Automata Make Ordinal Theory Easy
• Tight bounds on expected time to add correctly and add mostly correctly
• Title not available (Why is no real title available?)

This page was built for publication: Exact complexity bounds for ordinal addition

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