Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/142707
Title: The language preservation problem is undecidable for parametric event-recording automata
Authors: André, Étienne
Lin, Shang-Wei
Keywords: cs.FL
cs.FL
Engineering::Computer science and engineering
Issue Date: 2018
Source: André, É., & Lin, S.-W. (2018). The language preservation problem is undecidable for parametric event-recording automata. Information Processing Letters, 136, 17-20. doi:10.1016/j.ipl.2018.03.013
Journal: Information Processing Letters
Abstract: Parametric timed automata (PTA) extend timed automata with unknown constants ("parameters"), at the price of undecidability of most interesting problems. The (untimed) language preservation problem ("given a parameter valuation, can we find at least one other valuation with the same untimed language?") is undecidable for PTAs. We prove that this problem remains undecidable for parametric event-recording automata (PERAs), a subclass of PTAs that considerably restrains the way the language can be used; we also show it remains undecidable even for slightly different definitions of the language, i.e., finite sequences of actions ending in or passing infinitely often through accepting locations, or just all finite untimed words (without accepting locations).
URI: https://hdl.handle.net/10356/142707
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2018.03.013
Rights: © 2018 Elsevier B.V. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

SCOPUSTM   
Citations 50

1
Updated on Sep 30, 2022

Web of ScienceTM
Citations 50

1
Updated on Sep 29, 2022

Page view(s)

171
Updated on Oct 6, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.