Linear-Time Temporal Logic with Team Semantics: Expressivity and Complexity (English)
Free access
- New search for: Virtema, Jonni
- Further information on Virtema, Jonni:
- https://orcid.org/0000-0002-1582-3718
- New search for: Hofmann, Jana
- Further information on Hofmann, Jana:
- https://orcid.org/0000-0003-1660-2949
- New search for: Finkbeiner, Bernd
- Further information on Finkbeiner, Bernd:
- https://orcid.org/0000-0002-4280-8441
- New search for: Kontinen, Juha
- Further information on Kontinen, Juha:
- https://orcid.org/0000-0003-0115-5154
- New search for: Yang, Fan
- Further information on Yang, Fan:
- https://orcid.org/0000-0003-0392-6522
- New search for: Virtema, Jonni
- Further information on Virtema, Jonni:
- https://orcid.org/0000-0002-1582-3718
- New search for: Hofmann, Jana
- Further information on Hofmann, Jana:
- https://orcid.org/0000-0003-1660-2949
- New search for: Finkbeiner, Bernd
- Further information on Finkbeiner, Bernd:
- https://orcid.org/0000-0002-4280-8441
- New search for: Kontinen, Juha
- Further information on Kontinen, Juha:
- https://orcid.org/0000-0003-0115-5154
- New search for: Yang, Fan
- Further information on Yang, Fan:
- https://orcid.org/0000-0003-0392-6522
- New search for: Bojańczyk, Mikołaj
- New search for: Chekuri, Chandra
In:
LIPIcs, Volume 213, FSTTCS 2021
: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
;
213
;
52:1-52:17
;
2021
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Linear-Time Temporal Logic with Team Semantics: Expressivity and Complexity
-
Contributors:Virtema, Jonni ( author ) / Hofmann, Jana ( author ) / Finkbeiner, Bernd ( author ) / Kontinen, Juha ( author ) / Yang, Fan ( author ) / Bojańczyk, Mikołaj ( editor ) / Chekuri, Chandra ( editor )
-
Published in:LIPIcs, Volume 213, FSTTCS 2021 : 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) ; 213 ; 52:1-52:17Leibniz International Proceedings in Informatics (LIPIcs) ; 213 ; 52:1-52:17
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2021-11-29
-
Size:17 pages , 825458 byte
-
Remarks:LIPIcs, Vol. 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), pages 52:1-52:17
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
BQP After 28 Years (Invited Talk)Aaronson, Scott et al. | 2021
- 2
-
State Complexity of Population Protocols (Invited Talk)Esparza, Javier et al. | 2021
- 3
-
Approximately Counting Graph Homomorphisms and Retractions (Invited Talk)Goldberg, Leslie Ann et al. | 2021
- 4
-
Indistinguishability Obfuscation from Well-Founded Assumptions (Invited Talk)Lin, Huijia (Rachel) et al. | 2021
- 5
-
The Complexity of Gradient Descent (Invited Talk)Savani, Rahul et al. | 2021
- 6
-
Scheduling in the Secretary ModelAlbers, Susanne / Janke, Maximilian et al. | 2021
- 7
-
One-Way Functions and a Conditional Variant of MKTPAllender, Eric / Cheraghchi, Mahdi / Myrisiotis, Dimitrios / Tirumala, Harsha / Volkovich, Ilya et al. | 2021
- 8
-
Generalizations of Length Limited Huffman Coding for Hierarchical Memory SettingsBanchhor, Shashwat / Gajjala, Rishikesh / Sabharwal, Yogish / Sen, Sandeep et al. | 2021
- 9
-
Approximation Algorithms for Flexible Graph ConnectivityBoyd, Sylvia / Cheriyan, Joseph / Haddadan, Arash / Ibrahimpur, Sharat et al. | 2021
- 10
-
Tight Chang’s-Lemma-Type Bounds for Boolean FunctionsChakraborty, Sourav / Mande, Nikhil S. / Mittal, Rajat / Molli, Tulasimohan / Paraashar, Manaswi / Sanyal, Swagato et al. | 2021
- 11
-
Approximate Trace Reconstruction via Median String (In Average-Case)Chakraborty, Diptarka / Das, Debarati / Krauthgamer, Robert et al. | 2021
- 12
-
Approximating the Center Ranking Under UlamChakraborty, Diptarka / Gajjar, Kshitij / Jha, Agastya Vibhuti et al. | 2021
- 13
-
Towards Stronger Counterexamples to the Log-Approximate-Rank ConjectureChattopadhyay, Arkadev / Garg, Ankit / Sherif, Suhail et al. | 2021
- 14
-
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth FourChillara, Suryajith et al. | 2021
- 15
-
On (Simple) Decision Tree RankDahiya, Yogesh / Mahajan, Meena et al. | 2021
- 16
-
Reachability and Matching in Single Crossing Minor Free GraphsDatta, Samir / Gupta, Chetan / Jain, Rahul / Mukherjee, Anish / Sharma, Vimal Raj / Tewari, Raghunath et al. | 2021
- 17
-
Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient FunctionDu, Yang / Volkovich, Ilya et al. | 2021
- 18
-
Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update TimeEberle, Franziska / Megow, Nicole / Nölke, Lukas / Simon, Bertrand / Wiese, Andreas et al. | 2021
- 19
-
Largest Similar Copies of Convex Polygons in Polygonal DomainsEom, Taekang / Lee, Seungjun / Ahn, Hee-Kap et al. | 2021
- 20
-
A Faster Algorithm for Finding Closest Pairs in Hamming MetricEsser, Andre / Kübler, Robert / Zweydinger, Floyd et al. | 2021
- 21
-
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial SpaceFomin, Fedor V. / Golovach, Petr A. / Inamdar, Tanmay / Saurabh, Saket et al. | 2021
- 22
-
On Fair and Efficient Allocations of Indivisible Public GoodsGarg, Jugal / Kulkarni, Pooja / Murhekar, Aniket et al. | 2021
- 23
-
Time Space Optimal Algorithm for Computing Separators in Bounded Genus GraphsGupta, Chetan / Jain, Rahul / Tewari, Raghunath et al. | 2021
- 24
-
Near-Optimal Cayley Expanders for Abelian GroupsJalan, Akhil / Moshkovitz, Dana et al. | 2021
- 25
-
Matchings, Critical Nodes, and Popular SolutionsKavitha, Telikepalli et al. | 2021
- 26
-
Fast and Exact Convex Hull SimplificationKlimenko, Georgiy / Raichel, Benjamin et al. | 2021
- 27
-
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common SubsequenceLi, Xin / Zheng, Yu et al. | 2021
- 28
-
An ETH-Tight Algorithm for Multi-Team FormationLokshtanov, Daniel / Saurabh, Saket / Suri, Subhash / Xue, Jie et al. | 2021
- 29
-
Dominating Set in Weakly Closed Graphs is Fixed Parameter TractableLokshtanov, Daniel / Surianarayanan, Vaishali et al. | 2021
- 30
-
Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower QuotasNasre, Meghana / Nimbhorkar, Prajakta / Ranjan, Keshav / Sarkar, Ankita et al. | 2021
- 31
-
Property B: Two-Coloring Non-Uniform HypergraphsRadhakrishnan, Jaikumar / Srinivasan, Aravind et al. | 2021
- 32
-
Harmonic Algorithms for Packing d-Dimensional Cuboids into BinsSharma, Eklavya et al. | 2021
- 33
-
Resilience of Timed SystemsAkshay, S. / Genest, Blaise / Hélouët, Loïc / Krishna, S. / Roychowdhury, Sparsa et al. | 2021
- 34
-
On the Complexity of Intersection Non-emptiness for Star-Free Language ClassesArrighi, Emmanuel / Fernau, Henning / Hoffmann, Stefan / Holzer, Markus / Jecker, Ismaël / de Oliveira Oliveira, Mateus / Wolf, Petra et al. | 2021
- 35
-
Complexity of Coverability in Bounded Path Broadcast NetworksBalasubramanian, A. R. et al. | 2021
- 36
-
On Classical Decidable Logics Extended with Percentage Quantifiers and ArithmeticsBednarczyk, Bartosz / Orłowska, Maja / Pacanowska, Anna / Tan, Tony et al. | 2021
- 37
-
Branching Automata and Pomset AutomataBedon, Nicolas et al. | 2021
- 38
-
History Determinism vs. Good for Gameness in Quantitative AutomataBoker, Udi / Lehtinen, Karoliina et al. | 2021
- 39
-
Local First-Order Logic with Two Data ValuesBollig, Benedikt / Sangnier, Arnaud / Stietel, Olivier et al. | 2021
- 40
-
Diagrammatic Polyhedral AlgebraBonchi, Filippo / Di Giorgio, Alessandro / Sobociński, Paweł et al. | 2021
- 41
-
From Local to Global Determinacy in Concurrent Graph GamesBordais, Benjamin / Bouyer, Patricia / Le Roux, Stéphane et al. | 2021
- 42
-
Quantitative Verification on Product Graphs of Small TreewidthChatterjee, Krishnendu / Ibsen-Jensen, Rasmus / Pavlogiannis, Andreas et al. | 2021
- 43
-
Synthesizing Computable Functions from Rational Specifications over Infinite WordsFiliot, Emmanuel / Winter, Sarah et al. | 2021
- 44
-
Confluence of Conditional Rewriting in Logic FormGutiérrez, Raúl / Lucas, Salvador / Vítores, Miguel et al. | 2021
- 45
-
On the Expressive Equivalence of TPTL in the Pointwise and Continuous SemanticsHolla, Raveendra / Deka, Nabarun / D'Souza, Deepak et al. | 2021
- 46
-
Separating Regular Languages over Infinite Words with Respect to the Wagner HierarchyHugenroth, Christopher et al. | 2021
- 47
-
Normal Sequences with Non-Maximal Automatic ComplexityJordon, Liam / Moser, Philippe et al. | 2021
- 48
-
Approximate Bisimulation MinimisationKiefer, Stefan / Tang, Qiyi et al. | 2021
- 49
-
Simple Derivation Systems for Proving Sufficient Completeness of Non-Terminating Term Rewriting SystemsKikuchi, Kentaro / Aoto, Takahito et al. | 2021
- 50
-
Parikh Images of Register AutomataLasota, Sławomir / Pattathurajan, Mohnish et al. | 2021
- 51
-
Concrete Categorical Model of a Quantum Circuit Description Language with MeasurementLee, Dongho / Perrelle, Valentin / Valiron, Benoît / Xu, Zhaowei et al. | 2021
- 52
-
Linear-Time Temporal Logic with Team Semantics: Expressivity and ComplexityVirtema, Jonni / Hofmann, Jana / Finkbeiner, Bernd / Kontinen, Juha / Yang, Fan et al. | 2021