Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The New Complexity Landscape Around Circuit Minimization Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

Approaching Arithmetic Theories with Finite-State Automata

verfasst von : Christoph Haase

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The automata-theoretic approach provides an elegant method for deciding linear arithmetic theories. This approach has recently been instrumental for settling long-standing open problems about the complexity of deciding the existential fragments of Büchi arithmetic and linear arithmetic over p-adic fields. In this article, which accompanies an invited talk, we give a high-level exposition of the NP upper bound for existential Büchi arithmetic, obtain some derived results, and further discuss some open problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases
Nächstes Kapitel Recompression: Technique for Word Equations and Compressed Data
Fußnoten
1
And for brevity, we do not delve into different ways of defining \(V_p(0)\), the results given work for any sensible choice of defining \(V_p(0)\).
 
2
For presentational convenience, we chose \(\mathbb {R}_+\) as the domain of BRW arithmetic, unlike [1] who actually use \(\mathbb {R}\).
 
Literatur
1.
Boigelot, B., Rassart, S., Wolper, P.: On the expressiveness of real and integer arithmetic automata (extended abstract). In: Automata, Languages and Programming, ICALP. Lect. Notes Comp. Sci., vol. 1443, pp. 152–163. Springer (1998)
2.
Boigelot, B., Wolper, P.: Representing arithmetic constraints with finite automata: An overview. In: Logic Programming, ICLP. Lect. Notes Comp. Sci., vol. 2401, pp. 1–19. Springer (2002)
3.
Boudet, A., Comon, H.: Diophantine equations, presburger arithmetic and finite automata. In: Trees in Algebra and Programming - CAAP. Lect. Notes Comp. Sci., vol. 1059, pp. 30–43. Springer (1996)
4.
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and \(p\)-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1(2), 191–238 (1994)MathSciNetCrossRef
5.
Durand-Gasselin, A., Habermehl, P.: On the use of non-deterministic automata for presburger arithmetic. In: Concurrency Theory - CONCUR. Lect. Notes Comp. Sci., vol. 6269, pp. 373–387. Springer (2010)
6.
Durand-Gasselin, A., Habermehl, P.: Ehrenfeucht-fraïssé goes elementarily automatic for structures of bounded degree. In: Symposium on Theoretical Aspects of Computer Science, STACS. LIPIcs, vol. 14, pp. 242–253. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)
7.
Ginsburg, S., Spanier, E.H.: Bounded ALGOL-like languages. T. Am. Math. Soc. pp. 333–368 (1964)
8.
Guépin, F., Haase, C., Worrell, J.: On the existential theories of Büchi arithmetic and linear \(p\)-adic fields. In: Logic in Computer Science, LICS. IEEE (2019)
9.
Klaedtke, F.: Bounds on the automata size for presburger arithmetic. ACM Trans. Comput. Log. 9(2), 11:1–11:34 (2008)
10.
Leroux, J., Point, G.: Tapas: The talence presburger arithmetic suite. In: Tools and Algorithms for the Construction and Analysis of Systems, TACAS. Lect. Notes Comp. Sci., vol. 5505, pp. 182–185. Springer (2009)
11.
Lipshitz, L.M.: Some remarks on the Diophantine problem for addition and divisibility. Proc. Model Theory Meeting. 33, 41–52 (1981)MathSciNetMATH
12.
Manders, K.L., Adleman, L.M.: NP-complete decision problems for binary quadratics. J. Comput. Syst. Sci. 16(2), 168–184 (1978)MathSciNetCrossRef
13.
Matthews, C.R.: Counting Points Modulo \(p\) for some Finitely Generated Subgroups of Algebraic Groups. Bull. Lond. Math. Soc. 14(2), 149–154 (1982)MathSciNetCrossRef
14.
McCurley, K.S.: The discrete logarithm problem. Proc. of Symp. in Applied Math. 42, 49–74 (1990)
15.
Scarpellini, B.: Complexity of subcases of Presburger arithmetic. T. Am. Math. Soc. 284, 203–218 (1984)
16.
17.
To, A.W.: Unary finite automata vs. arithmetic progressions. Inf. Process. Lett. 109(17), 1010–1014 (2009)
18.
Weispfenning, V.: The complexity of linear problems in fields. J. Symb. Comput. 5(1/2), 3–27 (1988)
19.
Wolper, P., Boigelot, B.: On the construction of automata from linear arithmetic constraints. In: Tools and Algorithms for the Construction and Analysis of Systems, TACAS. Lect. Notes Comp. Sci., vol. 1785, pp. 1–19. Springer (2000)
Metadaten
Titel
Approaching Arithmetic Theories with Finite-State Automata
verfasst von
Christoph Haase
Copyright-Jahr
2020
Buch
Language and Automata Theory and Applications

Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-40608-0_3

Premium Partner

    Bildnachweise