Interaction Graphs

DOI10.1145/3226594MaRDI QIDQ4691740zbMATH OpenOpenAlexFDO

Authors Thomas Seiller

Publication date 24 October 2018

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.07895

zbMATH Keywords

automatadynamic semanticsimplicit computational complexityinteraction graphslinear logicmeasurable dynamics

Mathematics Subject Classification ID

Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Abstract: This paper exhibits a series of semantic characterisations of sublinear nondeterministic complexity classes. These results fall into the general domain of logic-based approaches to complexity theory and so-called implicit computational complexity (ICC), i.e. descriptions of complexity classes without reference to specific machine models. In particular, it relates strongly to ICC results based on linear logic since the semantic framework considered stems from work on the latter. Moreover, the obtained characterisations are of a geometric nature: each class is characterised by a specific action of a group by measure-preserving maps.

Recommendations

• scientific article; zbMATH DE number 7604432
• Graph automata
• scientific article; zbMATH DE number 956808
• Interacting automata
• The complexity of interacting automata
• scientific article; zbMATH DE number 1886323
• scientific article; zbMATH DE number 2031101
• scientific article; zbMATH DE number 3848637
• scientific article; zbMATH DE number 3858446
• Interaction graphs of isomorphic automata networks. I: Complete digraph and minimum in-degree

Cited in

(5)

• The complexity of interacting automata
• Interaction graphs of isomorphic automata networks. I: Complete digraph and minimum in-degree
• Zeta functions and the (linear) logic of Markov processes
• Unifying lower bounds for algebraic machines, semantically
• Implicit automata in typed -calculi I: aperiodicity in a non-commutative logic

This page was built for publication: Interaction Graphs

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