32 Search Results for "Place, Thomas"

Document
DOI: 10.4230/LIPIcs.CSL.2024.45
A Generic Characterization of Generalized Unary Temporal Logic and Two-Variable First-Order Logic

Authors: Thomas Place and Marc Zeitoun

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
We study an operator on classes of languages. For each class 𝒞, it produces a new class FO²(𝕀_𝒞) associated with a variant of two-variable first-order logic equipped with a signature 𝕀_𝒞 built from 𝒞. For 𝒞 = {∅, A*}, we obtain the usual FO²(<)} logic, equipped with linear order. For 𝒞 = {∅,{ε},A+,A*}, we get the variant FO²(<,+1), which also includes the successor predicate. If 𝒞 consists of all Boolean combinations of languages A*aA*, where a is a letter, we get the variant FO²(< ,Bet), which includes "between" relations. We prove a generic algebraic characterization of the classes FO^2(𝕀_𝒞). It elegantly generalizes those known for all the cases mentioned above. Moreover, it implies that if 𝒞 has decidable separation (plus some standard properties), then FO²2(𝕀_𝒞) has a decidable membership problem. We actually work with an equivalent definition of FO²(𝕀_𝒞) in terms of unary temporal logic. For each class 𝒞, we consider a variant TL(𝒞) of unary temporal logic whose future/past modalities depend on 𝒞 and such that TL(𝒞) = FO²(𝕀_𝒞). Finally, we also characterize FL(𝒞) and PL(𝒞), the pure-future and pure-past restrictions of TL(𝒞). Like for TL(𝒞), these characterizations imply that if 𝒞 is a class with decidable separation, then FL(𝒞) and PL(𝒞) have decidable membership.
Cite as

Thomas Place and Marc Zeitoun. A Generic Characterization of Generalized Unary Temporal Logic and Two-Variable First-Order Logic. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 45:1-45:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{place_et_al:LIPIcs.CSL.2024.45,
  author =	{Place, Thomas and Zeitoun, Marc},
  title =	{{A Generic Characterization of Generalized Unary Temporal Logic and Two-Variable First-Order Logic}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{45:1--45:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.45},
  URN =		{urn:nbn:de:0030-drops-196888},
  doi =		{10.4230/LIPIcs.CSL.2024.45},
  annote =	{Keywords: Classes of regular languages, Generalized unary temporal logic, Generalized two-variable first-order logic, Generic decidable characterizations, Membership, Separation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.90
Quantum Proofs of Deletion for Learning with Errors

Authors: Alexander Poremba

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mutually incompatible observables cannot be measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds on this aspect of quantum mechanics to realize a cryptographic notion called certified deletion. While this remarkable notion enables a classical verifier to be convinced that a (private-key) quantum ciphertext has been deleted by an untrusted party, it offers no additional layer of functionality. In this work, we augment the proof-of-deletion paradigm with fully homomorphic encryption (FHE). We construct the first fully homomorphic encryption scheme with certified deletion - an interactive protocol which enables an untrusted quantum server to compute on encrypted data and, if requested, to simultaneously prove data deletion to a client. Our scheme has the desirable property that verification of a deletion certificate is public; meaning anyone can verify that deletion has taken place. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors (LWE) distribution in the form of a quantum state was deleted. As an application of our protocol, we construct a Dual-Regev public-key encryption scheme with certified deletion, which we then extend towards a (leveled) FHE scheme of the same type. We introduce the notion of Gaussian-collapsing hash functions - a special case of collapsing hash functions defined by Unruh (Eurocrypt 2016) - and we prove the security of our schemes under the assumption that the Ajtai hash function satisfies a certain strong Gaussian-collapsing property in the presence of leakage.
Cite as

Alexander Poremba. Quantum Proofs of Deletion for Learning with Errors. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 90:1-90:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{poremba:LIPIcs.ITCS.2023.90,
  author =	{Poremba, Alexander},
  title =	{{Quantum Proofs of Deletion for Learning with Errors}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{90:1--90:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.90},
  URN =		{urn:nbn:de:0030-drops-175934},
  doi =		{10.4230/LIPIcs.ITCS.2023.90},
  annote =	{Keywords: Learning with errors, certified deletion, fully homomorphic encryption}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.43
A Generic Polynomial Time Approach to Separation by First-Order Logic Without Quantifier Alternation

Authors: Thomas Place and Marc Zeitoun

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

Abstract
We look at classes of languages associated to fragments of first-order logic BΣ₁, in which quantifier alternations are disallowed. Each such fragment is fully determined by choosing the set of predicates on positions that may be used. Equipping first-order logic with the linear ordering and possibly the successor relation as predicates yields two natural fragments, which were investigated by Simon and Knast, who proved that these two variants have decidable membership: "does an input regular language belong to the class ?". We extend their results in two orthogonal directions. - First, instead of membership, we explore the more general separation problem: decide if two regular languages can be separated by a language from the class under study. - Second, we use more general inputs: classes 𝒢 of group languages (i.e., recognized by a DFA in which each letter induces a permutation of the states) and extensions thereof, written 𝒢^+. We rely on a characterization of BΣ₁ by the operator BPol: given an input class 𝒞, it outputs a class BPol(𝒞) that corresponds to a variant of BΣ₁ equipped with special predicates associated to 𝒞. The classes BPol(𝒢) and BPol(𝒢^+) capture many natural variants of BΣ₁ which use predicates such as the linear ordering, the successor, the modular predicates or the alphabetic modular predicates. We show that separation is decidable for BPol(𝒢) and BPol(𝒢^+) when this is the case for 𝒢. This was already known for BPol(𝒢) and for two particular classes of the form BPol(𝒢^+). Yet, the algorithms were indirect and relied on involved frameworks, yielding poor upper complexity bounds. In contrast, our approach is direct. We work only with elementary concepts (mainly, finite automata). Our main contribution consists in polynomial time Turing reductions from both BPol(𝒢)- and BPol(𝒢^+)-separation to 𝒢-separation. This yields polynomial time algorithms for several key variants of BΣ₁, including those equipped with the linear ordering and possibly the successor and/or the modular predicates.
Cite as

Thomas Place and Marc Zeitoun. A Generic Polynomial Time Approach to Separation by First-Order Logic Without Quantifier Alternation. 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. 43:1-43:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{place_et_al:LIPIcs.FSTTCS.2022.43,
  author =	{Place, Thomas and Zeitoun, Marc},
  title =	{{A Generic Polynomial Time Approach to Separation by First-Order Logic Without Quantifier Alternation}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{43:1--43:22},
  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.43},
  URN =		{urn:nbn:de:0030-drops-174356},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.43},
  annote =	{Keywords: Automata, Separation, Covering, Concatenation hierarchies, Group languages}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.51
A Note on the Join of Varieties of Monoids with LI

Authors: Nathan Grosshans

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In this note, we give a characterisation in terms of identities of the join of V with the variety of finite locally trivial semigroups LI for several well-known varieties of finite monoids V by using classical algebraic-automata-theoretic techniques. To achieve this, we use the new notion of essentially-V stamps defined by Grosshans, McKenzie and Segoufin and show that it actually coincides with the join of V and LI precisely when some natural condition on the variety of languages corresponding to V is verified. This work is a kind of rediscovery of the work of J. C. Costa around 20 years ago from a rather different angle, since Costa’s work relies on the use of advanced developments in profinite topology, whereas what is presented here essentially uses an algebraic, language-based approach.
Cite as

Nathan Grosshans. A Note on the Join of Varieties of Monoids with LI. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grosshans:LIPIcs.MFCS.2021.51,
  author =	{Grosshans, Nathan},
  title =	{{A Note on the Join of Varieties of Monoids with LI}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.51},
  URN =		{urn:nbn:de:0030-drops-144918},
  doi =		{10.4230/LIPIcs.MFCS.2021.51},
  annote =	{Keywords: Varieties of monoids, join, LI}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.ITP.2021.3
Bounded-Deducibility Security (Invited Paper)

Authors: Andrei Popescu, Thomas Bauereiss, and Peter Lammich

Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)

Abstract
We describe Bounded-Deducibility (BD) security, an expressive framework for the specification and verification of information-flow security. The framework grew by confronting concrete challenges of specifying and verifying fine-grained confidentiality properties in some realistic web-based systems. The concepts and theorems that constitute this framework have an eventful history of such "confrontations", often involving trial and error, which are reported in previous papers. This paper is the first to focus on the framework itself rather than the case studies, gathering in one place all the abstract results about BD security.
Cite as

Andrei Popescu, Thomas Bauereiss, and Peter Lammich. Bounded-Deducibility Security (Invited Paper). In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{popescu_et_al:LIPIcs.ITP.2021.3,
  author =	{Popescu, Andrei and Bauereiss, Thomas and Lammich, Peter},
  title =	{{Bounded-Deducibility Security}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.3},
  URN =		{urn:nbn:de:0030-drops-138982},
  doi =		{10.4230/LIPIcs.ITP.2021.3},
  annote =	{Keywords: Information-flow security, Unwinding proof method, Compositionality, Verification}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.44
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations

Authors: Guy Blanc, Jane Lange, and Li-Yang Tan

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Consider the following heuristic for building a decision tree for a function f : {0,1}^n → {± 1}. Place the most influential variable x_i of f at the root, and recurse on the subfunctions f_{x_i=0} and f_{x_i=1} on the left and right subtrees respectively; terminate once the tree is an ε-approximation of f. We analyze the quality of this heuristic, obtaining near-matching upper and lower bounds: - Upper bound: For every f with decision tree size s and every ε ∈ (0,1/2), this heuristic builds a decision tree of size at most s^O(log(s/ε)log(1/ε)). - Lower bound: For every ε ∈ (0,1/2) and s ≤ 2^Õ(√n), there is an f with decision tree size s such that this heuristic builds a decision tree of size s^Ω~(log s). We also obtain upper and lower bounds for monotone functions: s^O(√{log s}/ε) and s^Ω(∜{log s}) respectively. The lower bound disproves conjectures of Fiat and Pechyony (2004) and Lee (2009). Our upper bounds yield new algorithms for properly learning decision trees under the uniform distribution. We show that these algorithms - which are motivated by widely employed and empirically successful top-down decision tree learning heuristics such as ID3, C4.5, and CART - achieve provable guarantees that compare favorably with those of the current fastest algorithm (Ehrenfeucht and Haussler, 1989), and even have certain qualitative advantages. Our lower bounds shed new light on the limitations of these heuristics. Finally, we revisit the classic work of Ehrenfeucht and Haussler. We extend it to give the first uniform-distribution proper learning algorithm that achieves polynomial sample and memory complexity, while matching its state-of-the-art quasipolynomial runtime.
Cite as

Guy Blanc, Jane Lange, and Li-Yang Tan. Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 44:1-44:44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.ITCS.2020.44,
  author =	{Blanc, Guy and Lange, Jane and Tan, Li-Yang},
  title =	{{Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{44:1--44:44},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.44},
  URN =		{urn:nbn:de:0030-drops-117295},
  doi =		{10.4230/LIPIcs.ITCS.2020.44},
  annote =	{Keywords: Decision trees, Influence of variables, Analysis of boolean functions, Learning theory, Top-down decision tree heuristics}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.3
On Sorting with a Network of Two Stacks

Authors: Matúš Mihalák and Marc Pont

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
Sorting with stacks is a collection of problems that deal with sorting a sequence of numbers by pushing and popping the numbers to and from a given set of stacks. Multiple concrete decision or optimization questions are formed by restricting the access to the stacks. The motivation comes, e.g., from shunting train wagons in shunting yards, shunting trams in depots, or in stacking cargo containers on cargo ships or storage yards in transshipment terminals. We consider the problem of sorting a permutation of n integers 1,2,...,n using k >= 2 stacks. In this problem, elements from the input sequence are pushed one-by-one (in the order of the elements in the sequence) to one of the k stacks. At any time, an element from a stack can be popped and pushed to another stack; such an operation is called a shuffle. Also, at any time, an element can be popped from a stack and placed to the output sequence. We can only place the elements to the output in the increasing order of their value such that at the end the output is the ordered sequence of the elements. The problem asks to minimize the number of shuffles in the process. It is known that for k >= 4, the problem is NP-hard, and that there is no approximation algorithm unless P=NP. For k >= 3, it is known that at most O(n log n) shuffles are needed for any input sequence. For the case when k=2, there exist input sequences that require Omega(n^{2-epsilon}) shuffles, for any epsilon>0. Nothing substantially more is known for the case of k=2. In this paper, we study the following variant of the problem with k=2 stacks: no shuffle and no placement to the output sequence can happen before every element is in one of the two stacks. We show that our problem can be seen as the MinUnCut problem by providing a polynomial-time reduction, and thus we show that there exists a randomized O(sqrt{log n})-approximation algorithm and a deterministic O(log n)-approximation algorithm for our problem.
Cite as

Matúš Mihalák and Marc Pont. On Sorting with a Network of Two Stacks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mihalak_et_al:OASIcs.ATMOS.2019.3,
  author =	{Mihal\'{a}k, Mat\'{u}\v{s} and Pont, Marc},
  title =	{{On Sorting with a Network of Two Stacks}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{3:1--3:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.3},
  URN =		{urn:nbn:de:0030-drops-114159},
  doi =		{10.4230/OASIcs.ATMOS.2019.3},
  annote =	{Keywords: Sorting, Stacks, Optimization, Algorithms, Reduction, MinUnCut}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.126
On All Things Star-Free (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Thomas Place and Marc Zeitoun

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We investigate the star-free closure, which associates to a class of languages its closure under Boolean operations and marked concatenation. We prove that the star-free closure of any finite class and of any class of groups languages with decidable separation (plus mild additional properties) has decidable separation. We actually show decidability of a stronger property, called covering. This generalizes many results on the subject in a unified framework. A key ingredient is that star-free closure coincides with another closure operator where Kleene stars are also allowed in restricted contexts.
Cite as

Thomas Place and Marc Zeitoun. On All Things Star-Free (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 126:1-126:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{place_et_al:LIPIcs.ICALP.2019.126,
  author =	{Place, Thomas and Zeitoun, Marc},
  title =	{{On All Things Star-Free}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{126:1--126:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.126},
  URN =		{urn:nbn:de:0030-drops-107028},
  doi =		{10.4230/LIPIcs.ICALP.2019.126},
  annote =	{Keywords: Regular languages, separation problem, star-free closure, group languages}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.47
The Complexity of Separation for Levels in Concatenation Hierarchies

Authors: Thomas Place and Marc Zeitoun

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
We investigate the complexity of the separation problem associated to classes of regular languages. For a class C, C-separation takes two regular languages as input and asks whether there exists a third language in C which includes the first and is disjoint from the second. First, in contrast with the situation for the classical membership problem, we prove that for most classes C, the complexity of C-separation does not depend on how the input languages are represented: it is the same for nondeterministic finite automata and monoid morphisms. Then, we investigate specific classes belonging to finitely based concatenation hierarchies. It was recently proved that the problem is always decidable for levels 1/2 and 1 of any such hierarchy (with inefficient algorithms). Here, we build on these results to show that when the alphabet is fixed, there are polynomial time algorithms for both levels. Finally, we investigate levels 3/2 and 2 of the famous Straubing-Thérien hierarchy. We show that separation is PSpace-complete for level 3/2 and between PSpace-hard and EXPTime for level 2.
Cite as

Thomas Place and Marc Zeitoun. The Complexity of Separation for Levels in Concatenation Hierarchies. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{place_et_al:LIPIcs.FSTTCS.2018.47,
  author =	{Place, Thomas and Zeitoun, Marc},
  title =	{{The Complexity of Separation for Levels in Concatenation Hierarchies}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.47},
  URN =		{urn:nbn:de:0030-drops-99463},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.47},
  annote =	{Keywords: Regular languages, separation, concatenation hierarchies, complexity}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.54
Flexible Patterns of Place for Function-based Search of Space (Short Paper)

Authors: Emmanuel Papadakis, Andreas Petutschnig, and Thomas Blaschke

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Place is a human interpretation of space; it augments the latter with information related to human activities, services, emotions and so forth. Searching for places rather than traditional space-based search represents significant challenges. The most prevalent method of addressing place-related queries is based on placenames but has limited potential due to the vagueness of natural language and its tendency to lead to ambiguous interpretations. In previous work we proposed a system-oriented formalization of place that goes beyond placenames by introducing composition patterns of place. In this study, we introduce flexibility into these patterns in terms of what is necessarily or possibly included when describing the spatial composition of a place and propose a novel automated process of extracting these patterns relying on both theoretical and empirical knowledge. The proposed methodology is exemplified through the use case of locating all the shopping areas within London, UK.
Cite as

Emmanuel Papadakis, Andreas Petutschnig, and Thomas Blaschke. Flexible Patterns of Place for Function-based Search of Space (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 54:1-54:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{papadakis_et_al:LIPIcs.GISCIENCE.2018.54,
  author =	{Papadakis, Emmanuel and Petutschnig, Andreas and Blaschke, Thomas},
  title =	{{Flexible Patterns of Place for Function-based Search of Space}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{54:1--54:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.54},
  URN =		{urn:nbn:de:0030-drops-93825},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.54},
  annote =	{Keywords: Functions, Place, Patterns, Function-based search, Place-based GIS}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.137
Separating Without Any Ambiguity

Authors: Thomas Place and Marc Zeitoun

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

Abstract
We investigate a standard operator on classes of languages: unambiguous polynomial closure. We show that if C is a class of regular languages having some mild properties, the membership problem for its unambiguous polynomial closure UPol(C) reduces to the same problem for C. We give a new, self-contained and elementary proof of this result. We also show that unambiguous polynomial closure coincides with alternating left and right deterministic closure. Finally, if additionally C is finite, we show that the separation and covering problems are decidable for UPol(C).
Cite as

Thomas Place and Marc Zeitoun. Separating Without Any Ambiguity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 137:1-137:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{place_et_al:LIPIcs.ICALP.2018.137,
  author =	{Place, Thomas and Zeitoun, Marc},
  title =	{{Separating Without Any Ambiguity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{137:1--137:14},
  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.137},
  URN =		{urn:nbn:de:0030-drops-91419},
  doi =		{10.4230/LIPIcs.ICALP.2018.137},
  annote =	{Keywords: Regular languages, separation problem, decidable characterizations}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.13
Gathering by Repulsion

Authors: Prosenjit Bose and Thomas C. Shermer

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We consider a repulsion actuator located in an n-sided convex environment full of point particles. When the actuator is activated, all the particles move away from the actuator. We study the problem of gathering all the particles to a point. We give an O(n^2) time algorithm to compute all the actuator locations that gather the particles to one point with one activation, and an O(n) time algorithm to find a single such actuator location if one exists. We then provide an O(n) time algorithm to place the optimal number of actuators whose sequential activation results in the gathering of the particles when such a placement exists.
Cite as

Prosenjit Bose and Thomas C. Shermer. Gathering by Repulsion. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.SWAT.2018.13,
  author =	{Bose, Prosenjit and Shermer, Thomas C.},
  title =	{{Gathering by Repulsion}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.13},
  URN =		{urn:nbn:de:0030-drops-88397},
  doi =		{10.4230/LIPIcs.SWAT.2018.13},
  annote =	{Keywords: polygon, kernel, beacon attraction}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2017.21
Infinite-Duration Bidding Games

Authors: Guy Avni, Thomas A. Henzinger, and Ventsislav Chonev

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
Two-player games on graphs are widely studied in formal methods as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. Both players have separate budgets, which sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously, and a bid is legal if it does not exceed the available budget. The winner of the bidding pays his bid to the other player and moves the token. For reachability objectives, repeated bidding games have been studied and are called Richman games [Lazarus1999,Lazarus2012]. There, a central question is the existence and computation of threshold budgets; namely, a value t \in [0,1] such that if \PO's budget exceeds t, he can win the game, and if \PT's budget exceeds 1-t, he can win the game. We focus on parity games and mean-payoff games. We show the existence of threshold budgets in these games, and reduce the problem of finding them to Richman games. We also determine the strategy-complexity of an optimal strategy. Our most interesting result shows that memoryless strategies suffice for mean-payoff bidding games.
Cite as

Guy Avni, Thomas A. Henzinger, and Ventsislav Chonev. Infinite-Duration Bidding Games. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{avni_et_al:LIPIcs.CONCUR.2017.21,
  author =	{Avni, Guy and Henzinger, Thomas A. and Chonev, Ventsislav},
  title =	{{Infinite-Duration Bidding Games}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.21},
  URN =		{urn:nbn:de:0030-drops-77741},
  doi =		{10.4230/LIPIcs.CONCUR.2017.21},
  annote =	{Keywords: Bidding Games, Parity Games, Mean-Payoff Games, Richman Games}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.77
The Covering Problem: A Unified Approach for Investigating the Expressive Power of Logics

Authors: Thomas Place and Marc Zeitoun

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
An important endeavor in computer science is to precisely understand the expressive power of logical formalisms over discrete structures, such as words. Naturally, "understanding" is not a mathematical notion. Therefore, this investigation requires a concrete objective to capture such a notion. In the literature, the standard choice for this objective is the membership problem, whose aim is to find a procedure deciding whether an input regular language can be defined in the logic under study. This approach was cemented as the "right" one by the seminal work of Schuetzenberger, McNaughton and Papert on first-order logic and has been in use since then. However, membership questions are hard: for several important fragments, researchers have failed in this endeavor despite decades of investigation. In view of recent results on one of the most famous open questions, namely the quantifier alternation hierarchy of first-order logic, an explanation may be that membership is too restrictive as a setting. These new results were indeed obtained by considering more general problems than membership, taking advantage of the increased flexibility of the enriched mathematical setting. This opens a promising avenue of research and efforts have been devoted at identifying and solving such problems for natural fragments. However, until now, these problems have been ad hoc, most fragments relying on a specific one. A unique new problem replacing membership as the right one is still missing. The main contribution of this paper is a suitable candidate to play this role: the Covering Problem. We motivate this problem with three arguments. First, it admits an elementary set theoretic formulation, similar to membership. Second, we are able to reexplain or generalize all known results with this problem. Third, we develop a mathematical framework as well as a methodology tailored to the investigation of this problem.
Cite as

Thomas Place and Marc Zeitoun. The Covering Problem: A Unified Approach for Investigating the Expressive Power of Logics. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{place_et_al:LIPIcs.MFCS.2016.77,
  author =	{Place, Thomas and Zeitoun, Marc},
  title =	{{The Covering Problem: A Unified Approach for Investigating the Expressive Power of Logics}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{77:1--77:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.77},
  URN =		{urn:nbn:de:0030-drops-64857},
  doi =		{10.4230/LIPIcs.MFCS.2016.77},
  annote =	{Keywords: membership problem, separation problem, covering problem, regular languages, logics, decidable characterizations}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.66
Approximation and Hardness of Token Swapping

Authors: Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Given a graph G=(V,E) with V={1,...,n}, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^{o(n)} algorithm under the ETH. This is matched with a simple 2^{O(n*log(n))} algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.
Cite as

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and Hardness of Token Swapping. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{miltzow_et_al:LIPIcs.ESA.2016.66,
  author =	{Miltzow, Tillmann and Narins, Lothar and Okamoto, Yoshio and Rote, G\"{u}nter and Thomas, Antonis and Uno, Takeaki},
  title =	{{Approximation and Hardness of Token Swapping}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{66:1--66:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.66},
  URN =		{urn:nbn:de:0030-drops-64084},
  doi =		{10.4230/LIPIcs.ESA.2016.66},
  annote =	{Keywords: token swapping, minimum generator sequence, graph theory, NP-hardness, approximation algorithms}
}
  • Refine by Author
  • 8 Place, Thomas
  • 8 Zeitoun, Marc
  • 2 Slavik, Pavel
  • 1 Agotnes, Thomas
  • 1 Amer-Yahia, Sihem
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Formal languages and automata theory
  • 2 Theory of computation → Regular languages
  • 1 Information systems → Geographic information systems
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 4 separation problem
  • 3 Regular languages
  • 3 Separation
  • 3 decidable characterizations
  • 2 Automata
  • Show More...

  • Refine by Type
  • 32 document

  • Refine by Publication Year
  • 4 2018
  • 3 2005
  • 3 2006
  • 3 2011
  • 2 2008
  • 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