ML p(r)ior | Simulation Problems Over One-Counter Nets

Simulation Problems Over One-Counter Nets

2016-02-01
One-counter nets (OCN) are finite automata equipped with a counter that can store non-negative integer values, and that cannot be tested for zero. Equivalently, these are exactly 1-dimensional vector addition systems with states. We show that both strong and weak simulation preorder on OCN are PSPACE-complete.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-05-02

We study multiplayer quantitative reachability games played on a finite directed graph, where the ob… show more
PDF

Highlights - Most important sentences from the article

2019-04-10

Entropy games and matrix multiplication games have been recently introduced by Asarin et al. They mo… show more
PDF

Highlights - Most important sentences from the article

2018-07-02

We introduce a new setting where a population of agents, each modelled by a finite-state system, are… show more
PDF

Highlights - Most important sentences from the article

2017-09-18
1709.05859 | cs.GT

This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) a… show more
PDF

Highlights - Most important sentences from the article

2017-11-27
1711.09946 | cs.FL

We present efficient algorithms to reduce the size of nondeterministic B\"uchi word automata (NBA) a… show more
PDF

Highlights - Most important sentences from the article

2018-11-01
1811.00483 | cs.FL

We introduce a measure called width, quantifying the amount of nondeterminism in automata. Width gen… show more
PDF

Highlights - Most important sentences from the article

2019-04-01
1904.01113 | cs.SY

This paper is concerned with a subspace guarding game, which is a reach-avoid game, in high-dimensio… show more
PDF

Highlights - Most important sentences from the article

2019-04-23
1904.10226 | cs.FL

In this paper we consider the reachability problem for bounded branching VASS. Bounded VASS are a va… show more
PDF

Highlights - Most important sentences from the article

2018-02-21

We introduce two-player games which build words over infinite alphabets, and we study the problem of… show more
PDF

Highlights - Most important sentences from the article

2016-06-08

Freeze LTL is a temporal logic with registers that is suitable for specifying properties of data wor… show more
PDF

Highlights - Most important sentences from the article

2015-10-19

We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some w… show more
PDF

Highlights - Most important sentences from the article

2019-02-19

This work contributes to the study of rewrite games where positions are words and the moves are loca… show more
PDF

Highlights - Most important sentences from the article

2018-09-27

Synthesis of finite-state controllers from high-level specifications in multi-agent systems can be r… show more
PDF

Highlights - Most important sentences from the article

2018-12-03

Weighted timed games are zero-sum games played by two players on a timed automaton equipped with wei… show more
PDF

Highlights - Most important sentences from the article

2018-11-13

In this paper we introduce a notion of fault-tolerance distance between labeled transition systems. … show more
PDF

Highlights - Most important sentences from the article

2014-10-17
1410.5703 | cs.LO

Mean-payoff games play a central role in quantitative synthesis and verification. In a single-dimens… show more
PDF

Highlights - Most important sentences from the article