License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.41
URN: urn:nbn:de:0030-drops-57422
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5742/
Go to the corresponding LIPIcs Volume Portal

Haase, Christoph ; Hofman, Piotr

Tightening the Complexity of Equivalence Problems for Commutative Grammars

pdf-format:
42.pdf (0.7 MB)

Abstract

Given two finite-state automata, are the Parikh images of the languages they generate equivalent? This problem was shown decidable in coNEXP by Huynh in 1985 within the more general setting of context-free commutative grammars. Huynh conjectured that a Pi_2^P upper bound might be possible, and Kopczynski and To established in 2010 such an upper bound when the size of the alphabet is fixed. The contribution of this paper is to show that the language equivalence problem for regular and context-free commutative grammars is actually coNEXP-complete. In addition, our lower bound immediately yields further coNEXP-completeness results for equivalence problems for regular commutative expressions, reversal-bounded counter automata and communication-free Petri nets. Finally, we improve both lower and upper bounds for language equivalence for exponent-sensitive commutative grammars.

BibTeX - Entry

@InProceedings{haase_et_al:LIPIcs:2016:5742,
  author =	{Christoph Haase and Piotr Hofman},
  title =	{{Tightening the Complexity of Equivalence Problems for Commutative Grammars}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5742},
  URN =		{urn:nbn:de:0030-drops-57422},
  doi =		{10.4230/LIPIcs.STACS.2016.41},
  annote =	{Keywords: language equivalence, commutative grammars, presburger arithmetic, semi-linear sets, petri nets}
}

Keywords: language equivalence, commutative grammars, presburger arithmetic, semi-linear sets, petri nets
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI