The Parametric Complexity of Lossy Counter Machines
From MaRDI portal
Publication:5092331
DOI10.4230/LIPIcs.ICALP.2019.129OpenAlexW2918439752MaRDI QIDQ5092331
Publication date: 21 July 2022
Full work available at URL: https://hal.archives-ouvertes.fr/hal-02020728
Cites Work
- Unnamed Item
- Unnamed Item
- The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
- Ordinal recursive complexity of unordered data nets
- Linearizing well quasi-orders and bounding the length of bad sequences
- Petri nets and large finite sets
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- Ordinal recursive bounds for Higman's theorem
- Recursivite et cônes rationnels fermés par intersection
- Undecidable problems in unreliable computations.
- On the finite containment problem for Petri nets
- Verifying lossy channel systems has nonprimitive recursive complexity.
- Algorithmic analysis of programs with well quasi-ordered domains.
- Complexity bounds for some finite forms of Kruskal's theorem
- Verifying programs with unreliable channels
- The theory of well-quasi-ordering: a frequently discovered concept
- Trace inclusion for one-counter nets revisited
- History-Register Automata
- On Freeze LTL with Ordered Attributes
- Complexity Hierarchies beyond Elementary
- The Power of Well-Structured Systems
- LTL with the freeze quantifier and register automata
- Nonelementary Complexities for Branching VASS, MELL, and Extensions
- The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
- Multiply-Recursive Upper Bounds with Higman’s Lemma
- Proofs and Computations
- Future-Looking Logics on Data Words and Trees
- Lossy Counter Machines Decidability Cheat Sheet
- Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
- Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals
- The Complexity of the Finite Containment Problem for Petri Nets
- Senescent ground tree rewrite systems
- The Complexity of Coverability in ν-Petri Nets
- The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
- The complexity of decision procedures in relevance logic II
- Zeno, Hercules, and the Hydra
- Hierarchies of number-theoretic functions. I
- Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
- Ordering by Divisibility in Abstract Algebras
- The Power of Priority Channel Systems
- Well-structured transition systems everywhere!
This page was built for publication: The Parametric Complexity of Lossy Counter Machines
