Kleene star, subexponentials without contraction, and infinite computations

DOI10.33048/SEMI.2021.18.069MaRDI QIDQ2234420zbMATH OpenOpenAlexFDO

Authors Stepan Kuznetsov

Publication date 19 October 2021

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL https://doi.org/10.33048/semi.2021.18.069

zbMATH Keywords

complexityinnite computationsKleene starlinear logic

Mathematics Subject Classification ID

Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Recommendations

• Infinitary action logic with exponentiation
• Subexponentials in non-commutative linear logic
• Explorations in Subexponential Non-associative Non-commutative Linear Logic
• A \(\varPi_1^0\)-bounded fragment of infinitary action logic with exponential
• Decision problems for linear logic with least and greatest fixed points

Cites work

• A completeness theorem for Kleene algebras and the algebra of regular events
• A decade of concurrency. Reflections and perspectives. REX School/ Symposium, Noordwijkerhout, the Netherlands, June 1-4, 1993. Proceedings
• A general proof system for modalities in concurrent constraint programming
• A logical framework with commutative and non-commutative subexponentials
• Algebras for iteration and infinite computations
• An infinitary sequent system for the equational theory of *-continuous action lattices
• Decision problems for propositional linear logic
• scientific article; zbMATH DE number 4055576 (Why is no real title available?)
• scientific article; zbMATH DE number 549971 (Why is no real title available?)
• Infinitary action logic: complexity, models and grammars
• Lambek calculus is NP-complete
• Logic, language, and security. Essays dedicated to Andre Scedrov on the occasion of his 65th birthday.
• Non-terminating processes in the situation calculus
• Non-wellfounded proof theory for (Kleene+action)(algebras+lattices)
• On Action Logic: Equational Theories of Action Algebras
• On the complexity of reasoning in Kleene algebra
• Product-free Lambek calculus and context-free grammars
• Product-free Lambek calculus is NP-complete
• PSPACE-completeness of a thread criterion for circular proofs in linear logic with least and greatest fixed points
• Subexponential concurrent constraint programming
• Subexponentials in non-commutative linear logic
• The Lambek calculus enriched with additional connectives
• Types for Proofs and Programs
• Unidirectional Lambek grammars in polynomial time

Cited in

(5)

• Infinite time extensions of Kleene's \({\mathcal O}\)
• A \(\varPi_1^0\)-bounded fragment of infinitary action logic with exponential
• Infinitary action logic with exponentiation
• Algorithmic complexity for theories of commutative Kleene algebras
• Algorithmic complexity of theories with Kleene iteration

This page was built for publication: Kleene star, subexponentials without contraction, and infinite computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234420)