Ehrenfeucht-Fraïssé goes automatic for real addition

DOI10.1016/j.ic.2010.07.003zbMath1204.68121OpenAlexW1963694783MaRDI QIDQ710741

Felix Klaedtke

Publication date: 22 October 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.07.003

zbMATH Keywords

complexityupper boundsautomata theoryautomatic structuresautomata-based decision procedures for logical theoriesfirst-order equivalencelinear arithmetic over the realsminimal sizes of automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Uniformly Automatic Classes of Finite Structures

Uses Software

• MONA
• FAST
• LIRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-state \(\omega\)-languages
• Finite presentations of infinite structures: Automata and interpretations
• Theory of computation.
• MONA IMPLEMENTATION SECRETS
• Weak Second‐Order Arithmetic and Finite Automata
• Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract)
• Automatic Structures of Bounded Degree Revisited
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Application of model theoretic games to discrete linear orders and finite automata
• First-Order Queries on Finite Structures Over the Reals
• An effective decision procedure for linear arithmetic over the integers and reals
• Bounds on the automata size for Presburger arithmetic
• STACS 2004
• Automatic Structures: Richness and Limitations
• Presburger arithmetic with bounded quantifier alternation

This page was built for publication: Ehrenfeucht-Fraïssé goes automatic for real addition