Consequence-based and automata-based algorithms encompass two families of approaches that have been thoroughly studied as reasoning methods for many logical formalisms. While automata are useful for finding tight complexity bounds, consequence-based algorithms are typically simpler to describe, implement, and optimize. In this paper, we show that consequence-based reasoning can be reduced to the emptiness test of an appropriately built automaton. Thanks to this reduction, one can focus on developing efficient consequence-based algorithms, obtaining complexity bounds and other benefits of automata methods for free.

Hutschenreiter, L., Peñaloza, R. (2017). An automata view to goal-directed methods. In Proceedings of the 11th International Conference on Languages and Automata Theory and Applications (pp.103-114). Springer Verlag [10.1007/978-3-319-53733-7_7].

An automata view to goal-directed methods

Peñaloza, R
2017

Abstract

Consequence-based and automata-based algorithms encompass two families of approaches that have been thoroughly studied as reasoning methods for many logical formalisms. While automata are useful for finding tight complexity bounds, consequence-based algorithms are typically simpler to describe, implement, and optimize. In this paper, we show that consequence-based reasoning can be reduced to the emptiness test of an appropriately built automaton. Thanks to this reduction, one can focus on developing efficient consequence-based algorithms, obtaining complexity bounds and other benefits of automata methods for free.
paper
automata theory, reasoning methods
English
11th International Conference on Language and Automata Theory and Applications
2017
Drewes, F; Martin-Vide, C; Truthe, B
Proceedings of the 11th International Conference on Languages and Automata Theory and Applications
9783319537320
2017
10168
103
114
open
Hutschenreiter, L., Peñaloza, R. (2017). An automata view to goal-directed methods. In Proceedings of the 11th International Conference on Languages and Automata Theory and Applications (pp.103-114). Springer Verlag [10.1007/978-3-319-53733-7_7].
File in questo prodotto:
File Dimensione Formato  
HuPe17.pdf

accesso aperto

Tipologia di allegato: Author’s Accepted Manuscript, AAM (Post-print)
Dimensione 325.31 kB
Formato Adobe PDF
325.31 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/258639
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
Social impact