Heuristics for ROSA’s LTS searching

Fernando López Pelayo; Fernando Cuartero Gomez; Diego Cazorla; Pedro Valero-Lara; Mercedes Garcia Merayo

doi:10.1007/978-3-319-59147-6_37

Heuristics for ROSA’s LTS searching

Fernando López Pelayo
, Fernando Cuartero Gomez
, Diego Cazorla
, Pedro Valero-Lara
, Mercedes Garcia Merayo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The authors have been aimed by the goal of reducing the computational cost of searching the Labeled Transition Systems, LTSs, generated by Process Algebras. In particular, we have been following the idea of moving the order of the computational cost required to find/reach a desired node/state from the exponential of the classical Breadth-First Search fashion to the polynomial produced either by the Depth-First Search or by the A^∗ algorithm [6]. As usual, they both take as size of the problem the branching factor of the LTS. This paper, first, presents the Normal Formed ROSA processes required to, second, define a sound topological structure over this Process Algebra. The underlying notion of distance from this topology can be taken as the heuristics to guide the search for whatever node which reachability want to be studied, by means of an A^∗ algorithm.

Original language	English
Title of host publication	Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings
Editors	Ignacio Rojas, Andreu Catala, Gonzalo Joya
Publisher	Springer Verlag
Pages	427-437
Number of pages	11
ISBN (Print)	9783319591469
DOIs	https://doi.org/10.1007/978-3-319-59147-6_37
State	Published - 2017
Externally published	Yes
Event	16th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2017 - Zakopane, Poland Duration: Jun 11 2017 → Jun 15 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10306 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2017
Country/Territory	Poland
City	Zakopane
Period	06/11/17 → 06/15/17

Funding

F.L. Pelayo—Research supported by project TIN2015-65845-C3-2-R.

Keywords

AI searching
Computational complexity
Process Algebra

Access to Document

10.1007/978-3-319-59147-6_37

Cite this

Pelayo, F. L., Gomez, F. C., Cazorla, D., Valero-Lara, P., & Merayo, M. G. (2017). Heuristics for ROSA’s LTS searching. In I. Rojas, A. Catala, & G. Joya (Eds.), Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings (pp. 427-437). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10306 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-59147-6_37

Pelayo, Fernando López ; Gomez, Fernando Cuartero ; Cazorla, Diego et al. / Heuristics for ROSA’s LTS searching. Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings. editor / Ignacio Rojas ; Andreu Catala ; Gonzalo Joya. Springer Verlag, 2017. pp. 427-437 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ac5555c56e5e4deba3b530766bb1d379,

title = "Heuristics for ROSA{\textquoteright}s LTS searching",

abstract = "The authors have been aimed by the goal of reducing the computational cost of searching the Labeled Transition Systems, LTSs, generated by Process Algebras. In particular, we have been following the idea of moving the order of the computational cost required to find/reach a desired node/state from the exponential of the classical Breadth-First Search fashion to the polynomial produced either by the Depth-First Search or by the A∗ algorithm [6]. As usual, they both take as size of the problem the branching factor of the LTS. This paper, first, presents the Normal Formed ROSA processes required to, second, define a sound topological structure over this Process Algebra. The underlying notion of distance from this topology can be taken as the heuristics to guide the search for whatever node which reachability want to be studied, by means of an A∗ algorithm.",

keywords = "AI searching, Computational complexity, Process Algebra",

author = "Pelayo, \{Fernando L{\'o}pez\} and Gomez, \{Fernando Cuartero\} and Diego Cazorla and Pedro Valero-Lara and Merayo, \{Mercedes Garcia\}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 16th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2017 ; Conference date: 11-06-2017 Through 15-06-2017",

year = "2017",

doi = "10.1007/978-3-319-59147-6\_37",

language = "English",

isbn = "9783319591469",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "427--437",

editor = "Ignacio Rojas and Andreu Catala and Gonzalo Joya",

booktitle = "Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings",

}

Pelayo, FL, Gomez, FC, Cazorla, D, Valero-Lara, P & Merayo, MG 2017, Heuristics for ROSA’s LTS searching. in I Rojas, A Catala & G Joya (eds), Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10306 LNCS, Springer Verlag, pp. 427-437, 16th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2017, Zakopane, Poland, 06/11/17. https://doi.org/10.1007/978-3-319-59147-6_37

Heuristics for ROSA’s LTS searching. / Pelayo, Fernando López; Gomez, Fernando Cuartero; Cazorla, Diego et al.
Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings. ed. / Ignacio Rojas; Andreu Catala; Gonzalo Joya. Springer Verlag, 2017. p. 427-437 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10306 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Heuristics for ROSA’s LTS searching

AU - Pelayo, Fernando López

AU - Gomez, Fernando Cuartero

AU - Cazorla, Diego

AU - Valero-Lara, Pedro

AU - Merayo, Mercedes Garcia

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - The authors have been aimed by the goal of reducing the computational cost of searching the Labeled Transition Systems, LTSs, generated by Process Algebras. In particular, we have been following the idea of moving the order of the computational cost required to find/reach a desired node/state from the exponential of the classical Breadth-First Search fashion to the polynomial produced either by the Depth-First Search or by the A∗ algorithm [6]. As usual, they both take as size of the problem the branching factor of the LTS. This paper, first, presents the Normal Formed ROSA processes required to, second, define a sound topological structure over this Process Algebra. The underlying notion of distance from this topology can be taken as the heuristics to guide the search for whatever node which reachability want to be studied, by means of an A∗ algorithm.

AB - The authors have been aimed by the goal of reducing the computational cost of searching the Labeled Transition Systems, LTSs, generated by Process Algebras. In particular, we have been following the idea of moving the order of the computational cost required to find/reach a desired node/state from the exponential of the classical Breadth-First Search fashion to the polynomial produced either by the Depth-First Search or by the A∗ algorithm [6]. As usual, they both take as size of the problem the branching factor of the LTS. This paper, first, presents the Normal Formed ROSA processes required to, second, define a sound topological structure over this Process Algebra. The underlying notion of distance from this topology can be taken as the heuristics to guide the search for whatever node which reachability want to be studied, by means of an A∗ algorithm.

KW - AI searching

KW - Computational complexity

KW - Process Algebra

UR - https://www.scopus.com/pages/publications/85020859896

U2 - 10.1007/978-3-319-59147-6_37

DO - 10.1007/978-3-319-59147-6_37

M3 - Conference contribution

AN - SCOPUS:85020859896

SN - 9783319591469

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 427

EP - 437

BT - Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings

A2 - Rojas, Ignacio

A2 - Catala, Andreu

A2 - Joya, Gonzalo

PB - Springer Verlag

T2 - 16th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2017

Y2 - 11 June 2017 through 15 June 2017

ER -

Pelayo FL, Gomez FC, Cazorla D, Valero-Lara P, Merayo MG. Heuristics for ROSA’s LTS searching. In Rojas I, Catala A, Joya G, editors, Advances in Computational Intelligence - 14th International Work-Conference on Artificial Neural Networks, IWANN 2017, Proceedings. Springer Verlag. 2017. p. 427-437. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-59147-6_37

Heuristics for ROSA’s LTS searching

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this