Publication result detail

Towards Efficient Shape Analysis with Tree Automata

HOLÍK, L.; HRUŠKA, M.

Original Title

Towards Efficient Shape Analysis with Tree Automata

English Title

Towards Efficient Shape Analysis with Tree Automata

Type

Paper in proceedings (conference paper)

Original Abstract

We discuss our proposal of a formalism for representing classes of graphs based on tree automata. We aim at a formalism and an entailment algorithm that could be used in verification of pointer programs, that would be efficient, have well defined completeness guarantees, and be general. We believe that building the formalism on top of tree automata will make it possible to use existing advanced tree automata implementation techniques. We sketch the basic ideas behind the formalism and an entailment decision procedure, and outline some related research challenges.

English abstract

We discuss our proposal of a formalism for representing classes of graphs based on tree automata. We aim at a formalism and an entailment algorithm that could be used in verification of pointer programs, that would be efficient, have well defined completeness guarantees, and be general. We believe that building the formalism on top of tree automata will make it possible to use existing advanced tree automata implementation techniques. We sketch the basic ideas behind the formalism and an entailment decision procedure, and outline some related research challenges.

Keywords

Formal verification, shape analysis, tree automata

Key words in English

Formal verification, shape analysis, tree automata

Authors

HOLÍK, L.; HRUŠKA, M.

RIV year

2022

Released

02.12.2021

Publisher

Springer Verlag

Location

Cham

Book

Proceedings International Conference on Networked Systems

Edition

Lecture notes in Computer Science

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Number

12754

State

Federal Republic of Germany

Pages from

206

Pages to

214

Pages count

9

BibTex

@inproceedings{BUT176373,
  author="Lukáš {Holík} and Martin {Hruška}",
  title="Towards Efficient Shape Analysis with Tree Automata",
  booktitle="Proceedings International Conference on Networked Systems",
  year="2021",
  series="Lecture notes in Computer Science",
  journal="Lecture Notes in Computer Science",
  number="12754",
  pages="206--214",
  publisher="Springer Verlag",
  address="Cham",
  doi="10.1007/978-3-030-91014-3\{_}14",
  issn="0302-9743"
}