The Library
Finkel was right : counter-examples to several conjectures on variants of vector addition systems (invited talk)
Tools
Lazic, Ranko (2019) Finkel was right : counter-examples to several conjectures on variants of vector addition systems (invited talk). In: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), Bombay, India, 11-13 Dec 2019. Published in: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), 150 3:1-3:2. ISBN 9783959771313. doi:10.4230/LIPIcs.FSTTCS.2019.3 ISSN 1868-8969.
|
PDF
WRAP-Finkel-right-counter-examples-several-vector-systems-Lazic-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (280Kb) | Preview |
Official URL: http://drops.dagstuhl.de/opus/volltexte/2019/11565
Abstract
Studying one-dimensional grammar vector addition systems has long been advocated by Alain Finkel. In this presentation, we shall see how research on those systems has led to the recent breakthrough tower lower bound for the reachability problem on vector addition systems, obtained by Czerwinski et al. In fact, we shall look at how appropriate modifications of an underlying technical construction can lead to counter-examples to several conjectures on one-dimensional grammar vector addition systems, fixed-dimensional vector addition systems, and fixed-dimensional flat vector addition systems.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Petri nets, Vector analysis, Finkel, A. (Alain), 1958- , Computer science -- Mathematics, Computer systems -- Verification, Decidability (Mathematical logic) | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) | ||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
Place of Publication: | Dagstuhl, Germany | ||||||
ISBN: | 9783959771313 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 10 December 2019 | ||||||
Dates: |
|
||||||
Volume: | 150 | ||||||
Page Range: | 3:1-3:2 | ||||||
DOI: | 10.4230/LIPIcs.FSTTCS.2019.3 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 10 December 2019 | ||||||
Date of first compliant Open Access: | 13 December 2019 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Bombay, India | ||||||
Date(s) of Event: | 11-13 Dec 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year