Abstrakt. Vi anser pushdown timed automata (PTAs) som är tidsinställda automata (med täta klockor) förstärkt med en pushdown stack. En konfiguration av en PTA innehåller ett kontrolltillstånd, täta klockvärden och ett stackord. Genom att använda mönstertekniken ger vi en decidable karakterisering av den binära nåbarheten (dvs. uppsättningen av alla par av konfigurationer så att den ena kan nå den andra) av en PTA. Eftersom en tidsinställd automaton kan behandlas som en PTA utan pushdown stack, kan vi visa att binär räckvidd av en tidsinställd automaton är definierbar i additiv teori om reals och heltal. Resultaten kan användas för att verifiera en klass av egenskaper som innehåller linjära samband över både täta variabler och obundna diskreta variabler. Egenskaperna kunde tidigare inte verifieras med hjälp av den klassiska regiontekniken eller uttryckas med tidsinställda temporallogik för tidsinställda automata och CTL * för pushdown-system. Resultaten utvidgas också till andra generaliseringar av tidsinställd automata.
Dang REF har generaliserat resultatet av Comon och Jurski, vilket visar att den binära räckvidd relation för pushdown timed automata är definierbar i linjär aritmetik.
Pushdown Timed Automata: a Binary Reachability Characterization and Safety Verification
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}