Exact complexity bounds for ordinal addition

DOI10.1016/0304-3975(95)00221-9MaRDI QIDQ671516zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

• 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
• 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?)
• 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

(5)

• Tight bounds on expected time to add correctly and add mostly correctly
• Ehrenfeucht games and ordinal addition
• scientific article; zbMATH DE number 2087209 (Why is no real title available?)
• Complexity and (un)decidability of fragments of \(\langle \omega^{\omega^{\lambda}};\times\rangle\)
• Tree Automata Make Ordinal Theory Easy

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)