---
_id: '711'
abstract:
- lang: eng
text: Nested weighted automata (NWA) present a robust and convenient automata-theoretic
formalism for quantitative specifications. Previous works have considered NWA
that processed input words only in the forward direction. It is natural to allow
the automata to process input words backwards as well, for example, to measure
the maximal or average time between a response and the preceding request. We therefore
introduce and study bidirectional NWA that can process input words in both directions.
First, we show that bidirectional NWA can express interesting quantitative properties
that are not expressible by forward-only NWA. Second, for the fundamental decision
problems of emptiness and universality, we establish decidability and complexity
results for the new framework which match the best-known results for the special
case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality
is achieved at no additional computational complexity. This is in stark contrast
to the unweighted case, where bidirectional finite automata are no more expressive
but exponentially more succinct than their forward-only counterparts.
alternative_title:
- LIPIcs
article_number: '5'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
last_name: Otop
citation:
ama: 'Chatterjee K, Henzinger TA, Otop J. Bidirectional nested weighted automata.
In: Vol 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.CONCUR.2017.5'
apa: 'Chatterjee, K., Henzinger, T. A., & Otop, J. (2017). Bidirectional nested
weighted automata (Vol. 85). Presented at the 28th International Conference on
Concurrency Theory, CONCUR, Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Bidirectional
Nested Weighted Automata,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, “Bidirectional nested weighted
automata,” presented at the 28th International Conference on Concurrency Theory,
CONCUR, Berlin, Germany, 2017, vol. 85.
ista: Chatterjee K, Henzinger TA, Otop J. 2017. Bidirectional nested weighted automata.
28th International Conference on Concurrency Theory, CONCUR, LIPIcs, vol. 85,
5.
mla: Chatterjee, Krishnendu, et al. Bidirectional Nested Weighted Automata.
Vol. 85, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.CONCUR.2017.5.
short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017.
conference:
end_date: 2017-09-08
location: Berlin, Germany
name: 28th International Conference on Concurrency Theory, CONCUR
start_date: 2017-09-05
date_created: 2018-12-11T11:48:04Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2021-01-12T08:11:53Z
day: '01'
ddc:
- '004'
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2017.5
file:
- access_level: open_access
checksum: d2bda4783821a6358333fe27f11f4737
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:02Z
date_updated: 2020-07-14T12:47:49Z
file_id: '4661'
file_name: IST-2017-886-v1+1_LIPIcs-CONCUR-2017-5.pdf
file_size: 570294
relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
intvolume: ' 85'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6976'
pubrep_id: '886'
quality_controlled: '1'
scopus_import: 1
status: public
title: Bidirectional nested weighted automata
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 85
year: '2017'
...
---
_id: '712'
abstract:
- lang: eng
text: 'We establish a weak–strong uniqueness principle for solutions to entropy-dissipating
reaction–diffusion equations: As long as a strong solution to the reaction–diffusion
equation exists, any weak solution and even any renormalized solution must coincide
with this strong solution. Our assumptions on the reaction rates are just the
entropy condition and local Lipschitz continuity; in particular, we do not impose
any growth restrictions on the reaction rates. Therefore, our result applies to
any single reversible reaction with mass-action kinetics as well as to systems
of reversible reactions with mass-action kinetics satisfying the detailed balance
condition. Renormalized solutions are known to exist globally in time for reaction–diffusion
equations with entropy-dissipating reaction rates; in contrast, the global-in-time
existence of weak solutions is in general still an open problem–even for smooth
data–, thereby motivating the study of renormalized solutions. The key ingredient
of our result is a careful adjustment of the usual relative entropy functional,
whose evolution cannot be controlled properly for weak solutions or renormalized
solutions.'
author:
- first_name: Julian L
full_name: Fischer, Julian L
id: 2C12A0B0-F248-11E8-B48F-1D18A9856A87
last_name: Fischer
orcid: 0000-0002-0479-558X
citation:
ama: 'Fischer JL. Weak–strong uniqueness of solutions to entropy dissipating reaction–diffusion
equations. Nonlinear Analysis: Theory, Methods and Applications. 2017;159:181-207.
doi:10.1016/j.na.2017.03.001'
apa: 'Fischer, J. L. (2017). Weak–strong uniqueness of solutions to entropy dissipating
reaction–diffusion equations. Nonlinear Analysis: Theory, Methods and Applications.
Elsevier. https://doi.org/10.1016/j.na.2017.03.001'
chicago: 'Fischer, Julian L. “Weak–Strong Uniqueness of Solutions to Entropy Dissipating
Reaction–Diffusion Equations.” Nonlinear Analysis: Theory, Methods and Applications.
Elsevier, 2017. https://doi.org/10.1016/j.na.2017.03.001.'
ieee: 'J. L. Fischer, “Weak–strong uniqueness of solutions to entropy dissipating
reaction–diffusion equations,” Nonlinear Analysis: Theory, Methods and Applications,
vol. 159. Elsevier, pp. 181–207, 2017.'
ista: 'Fischer JL. 2017. Weak–strong uniqueness of solutions to entropy dissipating
reaction–diffusion equations. Nonlinear Analysis: Theory, Methods and Applications.
159, 181–207.'
mla: 'Fischer, Julian L. “Weak–Strong Uniqueness of Solutions to Entropy Dissipating
Reaction–Diffusion Equations.” Nonlinear Analysis: Theory, Methods and Applications,
vol. 159, Elsevier, 2017, pp. 181–207, doi:10.1016/j.na.2017.03.001.'
short: 'J.L. Fischer, Nonlinear Analysis: Theory, Methods and Applications 159 (2017)
181–207.'
date_created: 2018-12-11T11:48:05Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2021-01-12T08:11:55Z
day: '01'
department:
- _id: JuFi
doi: 10.1016/j.na.2017.03.001
intvolume: ' 159'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1703.00730
month: '08'
oa: 1
oa_version: Submitted Version
page: 181 - 207
publication: 'Nonlinear Analysis: Theory, Methods and Applications'
publication_identifier:
issn:
- 0362546X
publication_status: published
publisher: Elsevier
publist_id: '6975'
quality_controlled: '1'
scopus_import: 1
status: public
title: Weak–strong uniqueness of solutions to entropy dissipating reaction–diffusion
equations
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 159
year: '2017'
...
---
_id: '714'
abstract:
- lang: eng
text: Background HIV-1 infection and drug abuse are frequently co-morbid and their
association greatly increases the severity of HIV-1-induced neuropathology. While
nucleus accumbens (NAcc) function is severely perturbed by drugs of abuse, little
is known about how HIV-1 infection affects NAcc. Methods We used calcium and voltage
imaging to investigate the effect of HIV-1 trans-activator of transcription (Tat)
on rat NAcc. Based on previous neuronal studies, we hypothesized that Tat modulates
intracellular Ca2+ homeostasis of NAcc neurons. Results We provide evidence that
Tat triggers a Ca2+ signaling cascade in NAcc medium spiny neurons (MSN) expressing
D1-like dopamine receptors leading to neuronal depolarization. Firstly, Tat induced
inositol 1,4,5-trisphsophate (IP3) receptor-mediated Ca2+ release from endoplasmic
reticulum, followed by Ca2+ and Na+ influx via transient receptor potential canonical
channels. The influx of cations depolarizes the membrane promoting additional
Ca2+ entry through voltage-gated P/Q-type Ca2+ channels and opening of tetrodotoxin-sensitive
Na+ channels. By activating this mechanism, Tat elicits a feed-forward depolarization
increasing the excitability of D1-phosphatidylinositol-linked NAcc MSN. We previously
found that cocaine targets NAcc neurons directly (independent of the inhibition
of dopamine transporter) only when IP3-generating mechanisms are concomitantly
initiated. When tested here, cocaine produced a dose-dependent potentiation of
the effect of Tat on cytosolic Ca2+. Conclusion We describe for the first time
a HIV-1 Tat-triggered Ca2+ signaling in MSN of NAcc involving TRPC and depolarization
and a potentiation of the effect of Tat by cocaine, which may be relevant for
the reward axis in cocaine-abusing HIV-1-positive patients.
acknowledgement: This work was supported by the National Institutes of Health grants
DA035926 (to MEA), and P30DA013429 (to EMU).
article_processing_charge: No
article_type: original
author:
- first_name: Gabriela
full_name: Brailoiu, Gabriela
last_name: Brailoiu
- first_name: Elena
full_name: Deliu, Elena
id: 37A40D7E-F248-11E8-B48F-1D18A9856A87
last_name: Deliu
orcid: 0000-0002-7370-5293
- first_name: Jeffrey
full_name: Barr, Jeffrey
last_name: Barr
- first_name: Linda
full_name: Console Bram, Linda
last_name: Console Bram
- first_name: Alexandra
full_name: Ciuciu, Alexandra
last_name: Ciuciu
- first_name: Mary
full_name: Abood, Mary
last_name: Abood
- first_name: Ellen
full_name: Unterwald, Ellen
last_name: Unterwald
- first_name: Eugen
full_name: Brǎiloiu, Eugen
last_name: Brǎiloiu
citation:
ama: Brailoiu G, Deliu E, Barr J, et al. HIV Tat excites D1 receptor-like expressing
neurons from rat nucleus accumbens. Drug and Alcohol Dependence. 2017;178:7-14.
doi:10.1016/j.drugalcdep.2017.04.015
apa: Brailoiu, G., Deliu, E., Barr, J., Console Bram, L., Ciuciu, A., Abood, M.,
… Brǎiloiu, E. (2017). HIV Tat excites D1 receptor-like expressing neurons from
rat nucleus accumbens. Drug and Alcohol Dependence. Elsevier. https://doi.org/10.1016/j.drugalcdep.2017.04.015
chicago: Brailoiu, Gabriela, Elena Deliu, Jeffrey Barr, Linda Console Bram, Alexandra
Ciuciu, Mary Abood, Ellen Unterwald, and Eugen Brǎiloiu. “HIV Tat Excites D1 Receptor-like
Expressing Neurons from Rat Nucleus Accumbens.” Drug and Alcohol Dependence.
Elsevier, 2017. https://doi.org/10.1016/j.drugalcdep.2017.04.015.
ieee: G. Brailoiu et al., “HIV Tat excites D1 receptor-like expressing neurons
from rat nucleus accumbens,” Drug and Alcohol Dependence, vol. 178. Elsevier,
pp. 7–14, 2017.
ista: Brailoiu G, Deliu E, Barr J, Console Bram L, Ciuciu A, Abood M, Unterwald
E, Brǎiloiu E. 2017. HIV Tat excites D1 receptor-like expressing neurons from
rat nucleus accumbens. Drug and Alcohol Dependence. 178, 7–14.
mla: Brailoiu, Gabriela, et al. “HIV Tat Excites D1 Receptor-like Expressing Neurons
from Rat Nucleus Accumbens.” Drug and Alcohol Dependence, vol. 178, Elsevier,
2017, pp. 7–14, doi:10.1016/j.drugalcdep.2017.04.015.
short: G. Brailoiu, E. Deliu, J. Barr, L. Console Bram, A. Ciuciu, M. Abood, E.
Unterwald, E. Brǎiloiu, Drug and Alcohol Dependence 178 (2017) 7–14.
date_created: 2018-12-11T11:48:05Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2021-01-12T08:12:00Z
day: '01'
department:
- _id: GaNo
doi: 10.1016/j.drugalcdep.2017.04.015
external_id:
pmid:
- '28623807'
intvolume: ' 178'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5797705
month: '09'
oa: 1
oa_version: Submitted Version
page: 7 - 14
pmid: 1
publication: Drug and Alcohol Dependence
publication_identifier:
issn:
- '03768716'
publication_status: published
publisher: Elsevier
publist_id: '6967'
quality_controlled: '1'
scopus_import: 1
status: public
title: HIV Tat excites D1 receptor-like expressing neurons from rat nucleus accumbens
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 178
year: '2017'
...
---
_id: '715'
abstract:
- lang: eng
text: D-cycloserine ameliorates breathing abnormalities and survival rate in a mouse
model of Rett syndrome.
article_number: aao4218
author:
- first_name: Gaia
full_name: Novarino, Gaia
id: 3E57A680-F248-11E8-B48F-1D18A9856A87
last_name: Novarino
orcid: 0000-0002-7673-7178
citation:
ama: Novarino G. More excitation for Rett syndrome. Science Translational Medicine.
2017;9(405). doi:10.1126/scitranslmed.aao4218
apa: Novarino, G. (2017). More excitation for Rett syndrome. Science Translational
Medicine. American Association for the Advancement of Science. https://doi.org/10.1126/scitranslmed.aao4218
chicago: Novarino, Gaia. “More Excitation for Rett Syndrome.” Science Translational
Medicine. American Association for the Advancement of Science, 2017. https://doi.org/10.1126/scitranslmed.aao4218.
ieee: G. Novarino, “More excitation for Rett syndrome,” Science Translational
Medicine, vol. 9, no. 405. American Association for the Advancement of Science,
2017.
ista: Novarino G. 2017. More excitation for Rett syndrome. Science Translational
Medicine. 9(405), aao4218.
mla: Novarino, Gaia. “More Excitation for Rett Syndrome.” Science Translational
Medicine, vol. 9, no. 405, aao4218, American Association for the Advancement
of Science, 2017, doi:10.1126/scitranslmed.aao4218.
short: G. Novarino, Science Translational Medicine 9 (2017).
date_created: 2018-12-11T11:48:06Z
date_published: 2017-08-30T00:00:00Z
date_updated: 2021-01-12T08:12:04Z
day: '30'
department:
- _id: GaNo
doi: 10.1126/scitranslmed.aao4218
intvolume: ' 9'
issue: '405'
language:
- iso: eng
month: '08'
oa_version: None
publication: Science Translational Medicine
publication_identifier:
issn:
- '19466234'
publication_status: published
publisher: American Association for the Advancement of Science
publist_id: '6968'
quality_controlled: '1'
scopus_import: 1
status: public
title: More excitation for Rett syndrome
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2017'
...
---
_id: '716'
abstract:
- lang: eng
text: 'Two-player games on graphs are central in many problems in formal verification
and program analysis, such as synthesis and verification of open systems. In this
work, we consider solving recursive game graphs (or pushdown game graphs) that
model the control flow of sequential programs with recursion.While pushdown games
have been studied before with qualitative objectives-such as reachability and
?-regular objectives- in this work, we study for the first time such games with
the most well-studied quantitative objective, the mean-payoff objective. In pushdown
games, two types of strategies are relevant: (1) global strategies, which depend
on the entire global history; and (2) modular strategies, which have only local
memory and thus do not depend on the context of invocation but rather only on
the history of the current invocation of the module. Our main results are as follows:
(1) One-player pushdown games with mean-payoff objectives under global strategies
are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff
objectives under global strategies are undecidable. (3) One-player pushdown games
with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player
pushdown games with mean-payoff objectives under modular strategies can be solved
in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives
under modular strategies are NP-complete). We also establish the optimal strategy
complexity by showing that global strategies for mean-payoff objectives require
infinite memory even in one-player pushdown games and memoryless modular strategies
are sufficient in two-player pushdown games. Finally, we also show that all the
problems have the same complexity if the stack boundedness condition is added,
where along with the mean-payoff objective the player must also ensure that the
stack height is bounded.'
article_type: original
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: Chatterjee K, Velner Y. The complexity of mean-payoff pushdown games. Journal
of the ACM. 2017;64(5):34. doi:10.1145/3121408
apa: Chatterjee, K., & Velner, Y. (2017). The complexity of mean-payoff pushdown
games. Journal of the ACM. ACM. https://doi.org/10.1145/3121408
chicago: Chatterjee, Krishnendu, and Yaron Velner. “The Complexity of Mean-Payoff
Pushdown Games.” Journal of the ACM. ACM, 2017. https://doi.org/10.1145/3121408.
ieee: K. Chatterjee and Y. Velner, “The complexity of mean-payoff pushdown games,”
Journal of the ACM, vol. 64, no. 5. ACM, p. 34, 2017.
ista: Chatterjee K, Velner Y. 2017. The complexity of mean-payoff pushdown games.
Journal of the ACM. 64(5), 34.
mla: Chatterjee, Krishnendu, and Yaron Velner. “The Complexity of Mean-Payoff Pushdown
Games.” Journal of the ACM, vol. 64, no. 5, ACM, 2017, p. 34, doi:10.1145/3121408.
short: K. Chatterjee, Y. Velner, Journal of the ACM 64 (2017) 34.
date_created: 2018-12-11T11:48:06Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2021-01-12T08:12:08Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/3121408
ec_funded: 1
external_id:
arxiv:
- '1201.2829'
intvolume: ' 64'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1201.2829
month: '09'
oa: 1
oa_version: Preprint
page: '34'
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Journal of the ACM
publication_identifier:
issn:
- '00045411'
publication_status: published
publisher: ACM
publist_id: '6964'
quality_controlled: '1'
scopus_import: 1
status: public
title: The complexity of mean-payoff pushdown games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 64
year: '2017'
...