The complexity of downward closure comparisons

DOI10.4230/LIPICS.ICALP.2016.123zbMATH Open1388.68183arXiv1605.03149OpenAlexW2963604037MaRDI QIDQ4598265FDOQ4598265

Authors: Georg Zetzsche 

Publication date: 19 December 2017

Abstract: The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. Moreover, recent results show that downward closures are computable for quite powerful system models. One advantage of abstracting a language by its downward closure is that then equivalence and inclusion become decidable. In this work, we study the complexity of these two problems. More precisely, we consider the following decision problems: Given languages $K$ and $L$ from classes $mathcalC$ and $mathcalD$, respectively, does the downward closure of $K$ include (equal) that of $L$? These problems are investigated for finite automata, one-counter automata, context-free grammars, and reversal-bounded counter automata. For each combination, we prove a completeness result either for fixed or for arbitrary alphabets. Moreover, for Petri net languages, we show that both problems are Ackermann-hard and for higher-order pushdown automata of order~$k$, we prove hardness for complements of nondeterministic $k$-fold exponential time.

Full work available at URL: https://arxiv.org/abs/1605.03149

Recommendations

• An approach to computing downward closures
• Computing downward closures for stacked counter automata
• scientific article; zbMATH DE number 7204383
• The downward-closure of Petri net languages
• On the state complexity of closures and interiors of regular languages with subwords and superwords

zbMATH Keywords

complexityequivalenceinclusiondownward closures

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (17)

• The Complexity of the Diagonal Problem for Recursion Schemes
• Title not available (Why is that?)
• Unboundedness problems for machines with reversal-bounded counters
• Longest Common Subsequence with Gap Constraints
• Absent subsequences in words
• Cost Automata, Safe Schemes, and Downward Closures
• Ranking and Unranking k-Subsequence Universal Words
• Subsequences in bounded ranges: matching and analysis problems
• Existential Definability over the Subword Ordering
• An approach to computing downward closures
• Absent Subsequences in Words
• Scattered Factor-Universality of Words
• Combinatorial algorithms for subsequence matching: a survey
• The downward-closure of Petri net languages
• Computing downward closures for stacked counter automata
• The complexity of regular abstractions of one-counter languages
• On the state complexity of closures and interiors of regular languages with subwords and superwords

This page was built for publication: The complexity of downward closure comparisons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598265)