<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Complexity of Propositional Logics in Team Semantic

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 06 Jan 2018Embargo end date: 01 Jan 2015 Finland Publisher:Association for Computing Machinery (ACM)Journal:ACM Transactions on Computational Logic, volume 19, pages 1-14 (issn: 1529-3785, eissn: 1557-945X,

Authors: Hannula, Miika; Kontinen, Juha; Virtema, Jonni; Vollmer, Heribert;

doi: 10.1145/3157054 , 10.48550/arxiv.1504.06135

arXiv: http://arxiv.org/abs/1504.06135

handle: 10138/233124

Complexity of Propositional Logics in Team Semantic

- Summary
- Subjects
- Metrics

Abstract

We classify the computational complexity of the satisfiability, validity, and model-checking problems for propositional independence, inclusion, and team logic. Our main result shows that the satisfiability and validity problems for propositional team logic are complete for alternating exponential-time with polynomially many alternations.

Country

Finland

Related Organizations

University of Helsinki
Finland
University of Hannover
Germany

Keywords

INCLUSION LOGIC, FOS: Computer and information sciences, validity, Computer Science - Logic in Computer Science, independence, FINITE, Computational Complexity (cs.CC), cs.LO, MODAL DEPENDENCE LOGIC, FOS: Mathematics, cs.CC, INDEPENDENCE, dependence, Mathematics - Logic, model checking, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, math.LO, inclusion, satisfiability, team semantics, Propositional logic, Logic (math.LO), Mathematics

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	18
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%