2013 | OriginalPaper | Buchkapitel
Decision Problems for Additive Regular Functions
verfasst von : Rajeev Alur, Mukund Raghothaman
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Additive Cost Register Automata (ACRA) map strings to integers using a finite set of registers that are updated using assignments of the form “
x
: =
y
+
c
” at every step. The corresponding class of
additive regular functions
has multiple equivalent characterizations, appealing closure properties, and a decidable equivalence problem. In this paper, we solve two decision problems for this model. First, we define the
register complexity
of an additive regular function to be the minimum number of registers that an ACRA needs to compute it. We characterize the register complexity by a necessary and sufficient condition regarding the largest subset of registers whose values can be made far apart from one another. We then use this condition to design a
pspace
algorithm to compute the register complexity of a given ACRA, and establish a matching lower bound. Our results also lead to a machine-independent characterization of the register complexity of additive regular functions. Second, we consider
two-player games over ACRAs
, where the objective of one of the players is to reach a target set while minimizing the cost. We show the corresponding decision problem to be
exptime
-complete when the costs are non-negative integers, but undecidable when the costs are integers.