20 Search Results for "Ganardi, Moses"

Document
DOI: 10.4230/LIPIcs.STACS.2024.36
Directed Regular and Context-Free Languages

Authors: Moses Ganardi, Irmak Sağlam, and Georg Zetzsche

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We study the problem of deciding whether a given language is directed. A language L is directed if every pair of words in L have a common (scattered) superword in L. Deciding directedness is a fundamental problem in connection with ideal decompositions of downward closed sets. Another motivation is that deciding whether two directed context-free languages have the same downward closures can be decided in polynomial time, whereas for general context-free languages, this problem is known to be coNEXP-complete. We show that the directedness problem for regular languages, given as NFAs, belongs to AC¹, and thus polynomial time. Moreover, it is NL-complete for fixed alphabet sizes. Furthermore, we show that for context-free languages, the directedness problem is PSPACE-complete.
Cite as

Moses Ganardi, Irmak Sağlam, and Georg Zetzsche. Directed Regular and Context-Free Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.STACS.2024.36,
  author =	{Ganardi, Moses and Sa\u{g}lam, Irmak and Zetzsche, Georg},
  title =	{{Directed Regular and Context-Free Languages}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.36},
  URN =		{urn:nbn:de:0030-drops-197465},
  doi =		{10.4230/LIPIcs.STACS.2024.36},
  annote =	{Keywords: Subword, ideal, language, regular, context-free, equivalence, downward closure, compression}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.3
Context-Bounded Analysis of Concurrent Programs (Invited Talk)

Authors: Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Context-bounded analysis of concurrent programs is a technique to compute a sequence of under-approximations of all behaviors of the program. For a fixed bound k, a context bounded analysis considers only those runs in which a single process is interrupted at most k times. As k grows, we capture more and more behaviors of the program. Practically, context-bounding has been very effective as a bug-finding tool: many bugs can be found even with small bounds. Theoretically, context-bounded analysis is decidable for a large number of programming models for which verification problems are undecidable. In this paper, we survey some recent work in context-bounded analysis of multithreaded programs. In particular, we show a general decidability result. We study context-bounded reachability in a language-theoretic setup. We fix a class of languages (satisfying some mild conditions) from which each thread is chosen. We show context-bounded safety and termination verification problems are decidable iff emptiness is decidable for the underlying class of languages and context-bounded boundedness is decidable iff finiteness is decidable for the underlying class.
Cite as

Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. Context-Bounded Analysis of Concurrent Programs (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:LIPIcs.ICALP.2023.3,
  author =	{Baumann, Pascal and Ganardi, Moses and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg},
  title =	{{Context-Bounded Analysis of Concurrent Programs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.3},
  URN =		{urn:nbn:de:0030-drops-180559},
  doi =		{10.4230/LIPIcs.ICALP.2023.3},
  annote =	{Keywords: Context-bounded analysis, Multi-threaded programs, Decidability}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.110
Checking Refinement of Asynchronous Programs Against Context-Free Specifications

Authors: Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the language-theoretic approach to refinement verification, we check that the language of traces of an implementation all belong to the language of a specification. We consider the refinement verification problem for asynchronous programs against specifications given by a Dyck language. We show that this problem is EXPSPACE-complete - the same complexity as that of language emptiness and for refinement verification against a regular specification. Our algorithm uses several technical ingredients. First, we show that checking if the coverability language of a succinctly described vector addition system with states (VASS) is contained in a Dyck language is EXPSPACE-complete. Second, in the more technical part of the proof, we define an ordering on words and show a downward closure construction that allows replacing the (context-free) language of each task in an asynchronous program by a regular language. Unlike downward closure operations usually considered in infinite-state verification, our ordering is not a well-quasi-ordering, and we have to construct the regular language ab initio. Once the tasks can be replaced, we show a reduction to an appropriate VASS and use our first ingredient. In addition to the inherent theoretical interest, refinement verification with Dyck specifications captures common practical resource usage patterns based on reference counting, for which few algorithmic techniques were known.
Cite as

Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. Checking Refinement of Asynchronous Programs Against Context-Free Specifications. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 110:1-110:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:LIPIcs.ICALP.2023.110,
  author =	{Baumann, Pascal and Ganardi, Moses and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg},
  title =	{{Checking Refinement of Asynchronous Programs Against Context-Free Specifications}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{110:1--110:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.110},
  URN =		{urn:nbn:de:0030-drops-181622},
  doi =		{10.4230/LIPIcs.ICALP.2023.110},
  annote =	{Keywords: Asynchronous programs, VASS, Dyck languages, Language inclusion, Refinement verification}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.38
Low-Latency Sliding Window Algorithms for Formal Languages

Authors: Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For every regular language L it is shown that there exists a constant-latency solution that supports adding and removing symbols independently on both ends of the window (the so-called two-way variable-size model). We prove that this result extends to all visibly pushdown languages. For deterministic 1-counter languages we present a 𝒪(log n) latency sliding window algorithm for the two-way variable-size model where n refers to the window size. We complement these results with a conditional lower bound: there exists a fixed real-time deterministic context-free language L such that, assuming the OMV (online matrix vector multiplication) conjecture, there is no sliding window algorithm for L with latency n^(1/2-ε) for any ε > 0, even in the most restricted sliding window model (one-way fixed-size model). The above mentioned results all refer to the unit-cost RAM model with logarithmic word size. For regular languages we also present a refined picture using word sizes 𝒪(1), 𝒪(log log n), and 𝒪(log n).
Cite as

Moses Ganardi, Louis Jachiet, Markus Lohrey, and Thomas Schwentick. Low-Latency Sliding Window Algorithms for Formal Languages. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.FSTTCS.2022.38,
  author =	{Ganardi, Moses and Jachiet, Louis and Lohrey, Markus and Schwentick, Thomas},
  title =	{{Low-Latency Sliding Window Algorithms for Formal Languages}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{38:1--38:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-174301},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.38},
  annote =	{Keywords: Streaming algorithms, regular languages, context-free languages}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.124
Reachability in Bidirected Pushdown VASS

Authors: Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, and Georg Zetzsche

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
A pushdown vector addition system with states (PVASS) extends the model of vector addition systems with a pushdown store. A PVASS is said to be bidirected if every transition (pushing/popping a symbol or modifying a counter) has an accompanying opposite transition that reverses the effect. Bidirectedness arises naturally in many models; it can also be seen as a overapproximation of reachability. We show that the reachability problem for bidirected PVASS is decidable in Ackermann time and primitive recursive for any fixed dimension. For the special case of one-dimensional bidirected PVASS, we show reachability is in PSPACE, and in fact in polynomial time if the stack is polynomially bounded. Our results are in contrast to the directed setting, where decidability of reachability is a long-standing open problem already for one dimensional PVASS, and there is a PSPACE-lower bound already for one-dimensional PVASS with bounded stack. The reachability relation in the bidirected (stateless) case is a congruence over ℕ^d. Our upper bounds exploit saturation techniques over congruences. In particular, we show novel elementary-time constructions of semilinear representations of congruences generated by finitely many vector pairs. In the case of one-dimensional PVASS, we employ a saturation procedure over bounded-size counters. We complement our upper bound with a TOWER-hardness result for arbitrary dimension and k-EXPSPACE hardness in dimension 2k+6 using a technique by Lazić and Totzke to implement iterative exponentiations.
Cite as

Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, and Georg Zetzsche. Reachability in Bidirected Pushdown VASS. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 124:1-124:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.ICALP.2022.124,
  author =	{Ganardi, Moses and Majumdar, Rupak and Pavlogiannis, Andreas and Sch\"{u}tze, Lia and Zetzsche, Georg},
  title =	{{Reachability in Bidirected Pushdown VASS}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{124:1--124:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.124},
  URN =		{urn:nbn:de:0030-drops-164651},
  doi =		{10.4230/LIPIcs.ICALP.2022.124},
  annote =	{Keywords: Vector addition systems, Pushdown, Reachability, Decidability, Complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.7
Existential Definability over the Subword Ordering

Authors: Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam, and Georg Zetzsche

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study first-order logic (FO) over the structure consisting of finite words over some alphabet A, together with the (non-contiguous) subword ordering. In terms of decidability of quantifier alternation fragments, this logic is well-understood: If every word is available as a constant, then even the Σ₁ (i.e., existential) fragment is undecidable, already for binary alphabets A. However, up to now, little is known about the expressiveness of the quantifier alternation fragments: For example, the undecidability proof for the existential fragment relies on Diophantine equations and only shows that recursively enumerable languages over a singleton alphabet (and some auxiliary predicates) are definable. We show that if |A| ≥ 3, then a relation is definable in the existential fragment over A with constants if and only if it is recursively enumerable. This implies characterizations for all fragments Σ_i: If |A| ≥ 3, then a relation is definable in Σ_i if and only if it belongs to the i-th level of the arithmetical hierarchy. In addition, our result yields an analogous complete description of the Σ_i-fragments for i ≥ 2 of the pure logic, where the words of A^* are not available as constants.
Cite as

Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam, and Georg Zetzsche. Existential Definability over the Subword Ordering. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:LIPIcs.STACS.2022.7,
  author =	{Baumann, Pascal and Ganardi, Moses and Thinniyam, Ramanathan S. and Zetzsche, Georg},
  title =	{{Existential Definability over the Subword Ordering}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.7},
  URN =		{urn:nbn:de:0030-drops-158178},
  doi =		{10.4230/LIPIcs.STACS.2022.7},
  annote =	{Keywords: subword, subsequence, definability, expressiveness, first order logic, existential fragment, quantifier alternation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.45
Compression by Contracting Straight-Line Programs

Authors: Moses Ganardi

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In grammar-based compression a string is represented by a context-free grammar, also called a straight-line program (SLP), that generates only that string. We refine a recent balancing result stating that one can transform an SLP of size g in linear time into an equivalent SLP of size 𝒪(g) so that the height of the unique derivation tree is 𝒪(log N) where N is the length of the represented string (FOCS 2019). We introduce a new class of balanced SLPs, called contracting SLPs, where for every rule A → β₁ … β_k the string length of every variable β_i on the right-hand side is smaller by a constant factor than the string length of A. In particular, the derivation tree of a contracting SLP has the property that every subtree has logarithmic height in its leaf size. We show that a given SLP of size g can be transformed in linear time into an equivalent contracting SLP of size 𝒪(g) with rules of constant length. This result is complemented by a lower bound, proving that converting SLPs into so called α-balanced SLPs or AVL-grammars can incur an increase by a factor of Ω(log N). We present an application to the navigation problem in compressed unranked trees, represented by forest straight-line programs (FSLPs). A linear space data structure by Reh and Sieber (2020) supports navigation steps such as going to the parent, left/right sibling, or to the first/last child in constant time. We extend their solution by the operation of moving to the i-th child in time 𝒪(log d) where d is the degree of the current node. Contracting SLPs are also applied to the finger search problem over SLP-compressed strings where one wants to access positions near to a pre-specified finger position, ideally in 𝒪(log d) time where d is the distance between the accessed position and the finger. We give a linear space solution for the dynamic variant where one can set the finger in 𝒪(log N) time, and then access symbols or move the finger in time 𝒪(log d + log^(t) N) for any constant t where log^(t) N is the t-fold logarithm of N. This improves a previous solution by Bille, Christiansen, Cording, and Gørtz (2018) with access/move time 𝒪(log d + log log N).
Cite as

Moses Ganardi. Compression by Contracting Straight-Line Programs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganardi:LIPIcs.ESA.2021.45,
  author =	{Ganardi, Moses},
  title =	{{Compression by Contracting Straight-Line Programs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.45},
  URN =		{urn:nbn:de:0030-drops-146263},
  doi =		{10.4230/LIPIcs.ESA.2021.45},
  annote =	{Keywords: grammar-based compression, balancing, finger search}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.11
A Characterization of Wreath Products Where Knapsack Is Decidable

Authors: Pascal Bergsträßer, Moses Ganardi, and Georg Zetzsche

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group G and takes as input group elements g_1,…,g_n,g ∈ G and asks whether there are x_1,…,x_n ≥ 0 with g_1^{x_1}⋯ g_n^{x_n} = g. We study the knapsack problem for wreath products G≀H of groups G and H. Our main result is a characterization of those wreath products G≀H for which the knapsack problem is decidable. The characterization is in terms of decidability properties of the indiviual factors G and H. To this end, we introduce two decision problems, the intersection knapsack problem and its restriction, the positive intersection knapsack problem. Moreover, we apply our main result to H₃(ℤ), the discrete Heisenberg group, and to Baumslag-Solitar groups BS(1,q) for q ≥ 1. First, we show that the knapsack problem is undecidable for G≀H₃(ℤ) for any G ≠ 1. This implies that for G ≠ 1 and for infinite and virtually nilpotent groups H, the knapsack problem for G≀H is decidable if and only if H is virtually abelian and solvability of systems of exponent equations is decidable for G. Second, we show that the knapsack problem is decidable for G≀BS(1,q) if and only if solvability of systems of exponent equations is decidable for G.
Cite as

Pascal Bergsträßer, Moses Ganardi, and Georg Zetzsche. A Characterization of Wreath Products Where Knapsack Is Decidable. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bergstraer_et_al:LIPIcs.STACS.2021.11,
  author =	{Bergstr\"{a}{\ss}er, Pascal and Ganardi, Moses and Zetzsche, Georg},
  title =	{{A Characterization of Wreath Products Where Knapsack Is Decidable}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.11},
  URN =		{urn:nbn:de:0030-drops-136566},
  doi =		{10.4230/LIPIcs.STACS.2021.11},
  annote =	{Keywords: knapsack, wreath products, decision problems in group theory, decidability, discrete Heisenberg group, Baumslag-Solitar groups}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.102
Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis

Authors: Armin Weiß

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Goldmann and Russell (2002) initiated the study of the complexity of the equation satisfiability problem in finite groups by showing that it is in 𝖯 for nilpotent groups while it is 𝖭𝖯-complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups of Fitting length two. In this work, we present the first lower bounds for the equation satisfiability problem in finite solvable groups: under the assumption of the exponential time hypothesis, we show that it cannot be in 𝖯 for any group of Fitting length at least four and for certain groups of Fitting length three. Moreover, the same hardness result applies to the equation identity problem.
Cite as

Armin Weiß. Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 102:1-102:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wei:LIPIcs.ICALP.2020.102,
  author =	{Wei{\ss}, Armin},
  title =	{{Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{102:1--102:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.102},
  URN =		{urn:nbn:de:0030-drops-125093},
  doi =		{10.4230/LIPIcs.ICALP.2020.102},
  annote =	{Keywords: equations in groups, solvable groups, exponential time hypothesis}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.126
The Complexity of Knapsack Problems in Wreath Products

Authors: Michael Figelius, Moses Ganardi, Markus Lohrey, and Georg Zetzsche

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable groups. For a finitely generated group we study the so-called power word problem (does a given expression u₁^{k₁} … u_d^{k_d}, where u₁, …, u_d are words over the group generators and k₁, …, k_d are binary encoded integers, evaluate to the group identity?) and knapsack problem (does a given equation u₁^{x₁} … u_d^{x_d} = v, where u₁, …, u_d,v are words over the group generators and x₁,…,x_d are variables, have a solution in the natural numbers). We prove that the power word problem for wreath products of the form G ≀ ℤ with G nilpotent and iterated wreath products of free abelian groups belongs to TC⁰. As an application of the latter, the power word problem for free solvable groups is in TC⁰. On the other hand we show that for wreath products G ≀ ℤ, where G is a so called uniformly strongly efficiently non-solvable group (which form a large subclass of non-solvable groups), the power word problem is coNP-hard. For the knapsack problem we show NP-completeness for iterated wreath products of free abelian groups and hence free solvable groups. Moreover, the knapsack problem for every wreath product G ≀ ℤ, where G is uniformly efficiently non-solvable, is Σ₂^p-hard.
Cite as

Michael Figelius, Moses Ganardi, Markus Lohrey, and Georg Zetzsche. The Complexity of Knapsack Problems in Wreath Products. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 126:1-126:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{figelius_et_al:LIPIcs.ICALP.2020.126,
  author =	{Figelius, Michael and Ganardi, Moses and Lohrey, Markus and Zetzsche, Georg},
  title =	{{The Complexity of Knapsack Problems in Wreath Products}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{126:1--126:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.126},
  URN =		{urn:nbn:de:0030-drops-125339},
  doi =		{10.4230/LIPIcs.ICALP.2020.126},
  annote =	{Keywords: algorithmic group theory, knapsack, wreath product}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.21
Automatic Equivalence Structures of Polynomial Growth

Authors: Moses Ganardi and Bakhadyr Khoussainov

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
In this paper we study the class EqP of automatic equivalence structures of the form ?=(D, E) where the domain D is a regular language of polynomial growth and E is an equivalence relation on D. Our goal is to investigate the following two foundational problems (in the theory of automatic structures) aimed for the class EqP. The first is to find algebraic characterizations of structures from EqP, and the second is to investigate the isomorphism problem for the class EqP. We provide full solutions to these two problems. First, we produce a characterization of structures from EqP through multivariate polynomials. Second, we present two contrasting results. On the one hand, we prove that the isomorphism problem for structures from the class EqP is undecidable. On the other hand, we prove that the isomorphism problem is decidable for structures from EqP with domains of quadratic growth.
Cite as

Moses Ganardi and Bakhadyr Khoussainov. Automatic Equivalence Structures of Polynomial Growth. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.CSL.2020.21,
  author =	{Ganardi, Moses and Khoussainov, Bakhadyr},
  title =	{{Automatic Equivalence Structures of Polynomial Growth}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.21},
  URN =		{urn:nbn:de:0030-drops-116645},
  doi =		{10.4230/LIPIcs.CSL.2020.21},
  annote =	{Keywords: automatic structures, polynomial growth, isomorphism problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.6
Sliding Window Property Testing for Regular Languages

Authors: Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream ("the active window") belongs to a given regular language. Recent works [Moses Ganardi et al., 2018; Moses Ganardi et al., 2016] showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic or linear in the window size n and provided natural language theoretic characterizations of the space complexity classes. Subsequently, [Moses Ganardi et al., 2018] extended this result to randomized algorithms to show that any such algorithm admits either constant, double logarithmic, logarithmic or linear space complexity. In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We show that for every regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.
Cite as

Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.ISAAC.2019.6,
  author =	{Ganardi, Moses and Hucke, Danny and Lohrey, Markus and Starikovskaya, Tatiana},
  title =	{{Sliding Window Property Testing for Regular Languages}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.6},
  URN =		{urn:nbn:de:0030-drops-115023},
  doi =		{10.4230/LIPIcs.ISAAC.2019.6},
  annote =	{Keywords: Streaming algorithms, approximation algorithms, regular languages}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.29
Visibly Pushdown Languages over Sliding Windows

Authors: Moses Ganardi

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We investigate the class of visibly pushdown languages in the sliding window model. A sliding window algorithm for a language L receives a stream of symbols and has to decide at each time step whether the suffix of length n belongs to L or not. The window size n is either a fixed number (in the fixed-size model) or can be controlled by an adversary in a limited way (in the variable-size model). The main result of this paper states that for every visibly pushdown language the space complexity in the variable-size sliding window model is either constant, logarithmic or linear in the window size. This extends previous results for regular languages.
Cite as

Moses Ganardi. Visibly Pushdown Languages over Sliding Windows. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ganardi:LIPIcs.STACS.2019.29,
  author =	{Ganardi, Moses},
  title =	{{Visibly Pushdown Languages over Sliding Windows}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.29},
  URN =		{urn:nbn:de:0030-drops-102688},
  doi =		{10.4230/LIPIcs.STACS.2019.29},
  annote =	{Keywords: visibly pushdown languages, sliding windows, rational transductions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.15
Sliding Windows over Context-Free Languages

Authors: Moses Ganardi, Artur Jez, and Markus Lohrey

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study the space complexity of sliding window streaming algorithms that check membership of the window content in a fixed context-free language. For regular languages, this complexity is either constant, logarithmic or linear [Moses Ganardi et al., 2016]. We prove that every context-free language whose sliding window space complexity is log_2(n) - omega(1) must be regular and has constant space complexity. Moreover, for every c in N, c >= 1 we construct a (nondeterministic) context-free language whose sliding window space complexity is O(n^(1/c)) \ o(n^(1/c)). Finally, we give an example of a deterministic one-counter language whose sliding window space complexity is Theta((log n)^2).
Cite as

Moses Ganardi, Artur Jez, and Markus Lohrey. Sliding Windows over Context-Free Languages. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.MFCS.2018.15,
  author =	{Ganardi, Moses and Jez, Artur and Lohrey, Markus},
  title =	{{Sliding Windows over Context-Free Languages}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.15},
  URN =		{urn:nbn:de:0030-drops-95973},
  doi =		{10.4230/LIPIcs.MFCS.2018.15},
  annote =	{Keywords: sliding windows, streaming algorithms, context-free languages}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.127
Randomized Sliding Window Algorithms for Regular Languages

Authors: Moses Ganardi, Danny Hucke, and Markus Lohrey

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last n symbols. If the algorithm is randomized, then at each time instant it produces an incorrect output with probability at most epsilon, which is a constant error bound. This work proposes a more relaxed definition of correctness which is parameterized by the error bound epsilon and the failure ratio phi: a randomized sliding window algorithm is required to err with probability at most epsilon at a portion of 1-phi of all time instants of an input stream. This work continues the investigation of sliding window algorithms for regular languages. In previous works a trichotomy theorem was shown for deterministic algorithms: the optimal space complexity is either constant, logarithmic or linear in the window size. The main results of this paper concerns three natural settings (randomized algorithms with failure ratio zero and randomized/deterministic algorithms with bounded failure ratio) and provide natural language theoretic characterizations of the space complexity classes.
Cite as

Moses Ganardi, Danny Hucke, and Markus Lohrey. Randomized Sliding Window Algorithms for Regular Languages. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 127:1-127:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.ICALP.2018.127,
  author =	{Ganardi, Moses and Hucke, Danny and Lohrey, Markus},
  title =	{{Randomized Sliding Window Algorithms for Regular Languages}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{127:1--127:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.127},
  URN =		{urn:nbn:de:0030-drops-91317},
  doi =		{10.4230/LIPIcs.ICALP.2018.127},
  annote =	{Keywords: sliding windows, regular languages, randomized complexity}
}
  • Refine by Author
  • 19 Ganardi, Moses
  • 10 Lohrey, Markus
  • 8 Zetzsche, Georg
  • 5 Hucke, Danny
  • 3 Baumann, Pascal
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Problems, reductions and completeness
  • 4 Theory of computation → Streaming models
  • 3 Theory of computation → Concurrency
  • 2 Software and its engineering → Software verification
  • 2 Theory of computation → Formal languages and automata theory
  • Show More...

  • Refine by Keyword
  • 5 regular languages
  • 3 knapsack
  • 3 sliding windows
  • 2 Decidability
  • 2 Streaming algorithms
  • Show More...

  • Refine by Type
  • 20 document

  • Refine by Publication Year
  • 4 2018
  • 3 2020
  • 3 2022
  • 2 2016
  • 2 2019
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact