The complexity of downward closure comparisons

DOI10.4230/LIPICS.ICALP.2016.123MaRDI QIDQ4598265zbMATH OpenOpenAlexFDO

Authors Georg Zetzsche

Publication date 19 December 2017

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

zbMATH Keywords

complexitydownward closuresequivalenceinclusion

Mathematics Subject Classification ID

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

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.

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

Cited in

(37)

• Absent subsequences in words
• Computing downward closures for stacked counter automata
• An approach to computing downward closures
• The downward-closure of Petri net languages
• The complexity of regular abstractions of one-counter languages
• Scattered Factor-Universality of Words
• scientific article; zbMATH DE number 7204383 (Why is no real title available?)
• The Complexity of the Diagonal Problem for Recursion Schemes
• Cost Automata, Safe Schemes, and Downward Closures
• Absent Subsequences in Words
• Unboundedness problems for machines with reversal-bounded counters
• Ranking and Unranking k-Subsequence Universal Words
• Longest Common Subsequence with Gap Constraints
• Subsequences in bounded ranges: matching and analysis problems
• Existential Definability over the Subword Ordering
• Combinatorial algorithms for subsequence matching: a survey
• Cost automata, safe schemes, and downward closures
• Tight bounds for the number of absent subsequences
• Jumbled scattered factors
• Improved algorithm for reachability in d-VASS
• Subsequences with generalised gap constraints: upper and lower complexity bounds
• k-universality of regular languages revisited
• Directed regular and context-free languages
• Satisfiability of context-free string constraints with subword-ordering and transducers
• The edit distance to k-subsequence universality
• Counter machines with infrequent reversals
• \(k\)-universality of regular languages
• Longest common subsequence with gap constraints
• Priority downward closures
• Generalized Parikh matrices for tracking subsequence occurrences
• The edit distance to \(k\)-subsequence universality
• Efficiently testing Simon's congruence
• Subsequence matching and analysis problems for formal languages
• Linear time subsequence and supersequence regex matching
• The complexity of separability for semilinear sets and Parikh automata
• Scattered factor universality -- a survey
• 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)