We investigate the descriptive complexity of a class of neural networks with unrestricted topologies and piecewise polynomial activation functions. We consider the general scenario where the running time is unlimited ...
详细信息
ISBN:
(纸本)9783959773102
We investigate the descriptive complexity of a class of neural networks with unrestricted topologies and piecewise polynomial activation functions. We consider the general scenario where the running time is unlimited and floating-point numbers are used for simulating reals. We characterize these neural networks with a rule-based logic for Boolean networks. In particular, we show that the sizes of the neural networks and the corresponding Boolean rule formulae are polynomially related. In fact, in the direction from Boolean rules to neural networks, the blow-up is only linear. We also analyze the delays in running times due to the translations. In the translation from neural networks to Boolean rules, the time delay is polylogarithmic in the neural network size and linear in time. In the converse translation, the time delay is linear in both factors. We also obtain translations between the rule-based logic for Boolean networks, the diamond-free fragment of modal substitution calculus and a class of recursive Boolean circuits where the number of input and output gates match.
Two particularly active branches of research in constraint satisfaction are the study of promise constraint satisfaction problems (PCSPs) with finite templates and the study of infinite-domain constraint satisfaction ...
详细信息
ISBN:
(纸本)9783959773102
Two particularly active branches of research in constraint satisfaction are the study of promise constraint satisfaction problems (PCSPs) with finite templates and the study of infinite-domain constraint satisfaction problems with omega-categorical templates. In this paper, we explore some connections between these two hitherto unrelated fields and describe a general approach to studying the complexity of PCSPs by constructing suitable infinite CSP templates. As a result, we obtain new characterizations of the power of various classes of algorithms for PCSPs, such as first-order logic, arc consistency reductions, and obtain new proofs of the characterizations of the power of the classical linear and affine relaxations for PCSPs.
The proceedings contain 46 papers. The topics discussed include: Equi-rank homomorphism preservation theorem on finite structures;extension preservation on dense graph classes;the parameterized complexity of learning ...
ISBN:
(纸本)9783959773621
The proceedings contain 46 papers. The topics discussed include: Equi-rank homomorphism preservation theorem on finite structures;extension preservation on dense graph classes;the parameterized complexity of learning monadic second-order logic;on homogeneous models of fluted languages;on the expansion of monadic second-order logic with Cantor-Bendixson rank and order type predicates;first-order logic with equicardinality in random graphs;computational complexity of the Weisfeiler-Leman dimension;finite variable counting logics with restricted requantification;on the VC dimension of first-order logic with counting and weight aggregation;description complexity of unary structures in first-order logic with links to entropy;and reachability for multi-priced timed automata with positive and negative rates.
Quantified LTL (QLTL) extends the temporal logic LTL with quantifications over atomic propositions. Several semantics exist to handle these quantifications, depending on the definition of executions over which formula...
详细信息
ISBN:
(纸本)9783959773102
Quantified LTL (QLTL) extends the temporal logic LTL with quantifications over atomic propositions. Several semantics exist to handle these quantifications, depending on the definition of executions over which formulas are interpreted: either infinite sequences of subsets of atomic propositions (aka the "tree semantics") or infinite sequences of control states combined with a labelling function that associates atomic propositions to the control states (aka the "structure semantics"). The main difference being that in the latter different occurrences of a control state should be labelled similarly. The tree semantics has been intensively studied from the complexity and expressivity point of view (especially in the work of Sistla [21, 22]) for which the satisfiability and model-checking problems are known to be TOWER-complete. For the structure semantics, French has shown that the satisfiability problem is undecidable [8]. We study here the model-checking problem for QLTL under this semantics and prove that it is EXPSPACE-complete. We also show that the complexity drops down to PSPACE-complete for two specific cases of structures, namely path and flat ones.
The biennial "computersciences and Information Technologies" conference in Yerevan in September of 2023 was the 14th in this series. This event is of regional interest, provide a networking ecosystem to sci...
详细信息
The biennial "computersciences and Information Technologies" conference in Yerevan in September of 2023 was the 14th in this series. This event is of regional interest, provide a networking ecosystem to scientists in areas such as the Mathematical logic and logical Reasoning, Discrete Mathematics, Pattern Recognition and Cognitive sciences, and Applications. 17 selected papers of this conference, included in Special Issue of PRIA journal provide up to date research results and research topics that make a sensitive input to the field known as "logic Combinatorial Pattern Recognition". Results from Algebra and Mathematical logic help in structural and semantic areas of pattern recognition, graph theoretical investigations help with clustering and image analysis, other selected papers and results are devoted directly to semantic pattern recognition, to cognitive sciences in general, or they provide application platforms where different artificial intelligence technologies are converging.
This paper compares the time complexity of various sorting algorithms for the logic, code and time complexity of each algorithm. The sorting algorithms that this paper discusses are Selection sort, Bubble sort, Insert...
详细信息
Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve two-player games on directed graphs such as parity games and mean payoff games. In contrast to the usua...
详细信息
ISBN:
(纸本)9783959773102
Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve two-player games on directed graphs such as parity games and mean payoff games. In contrast to the usual well-known strategy improvement algorithm, it iterates over strategies of both players simultaneously. The symmetric version solves the known worst-case examples for strategy improvement quickly, however its worst-case complexity remained open. We present a class of worst-case examples for symmetric strategy improvement on which this symmetric version also takes exponentially many steps. Remarkably, our examples exhibit this behaviour for any choice of improvement rule, which is in contrast to classical strategy improvement where hard instances are usually hand-crafted for a specific improvement rule. We present a generalized version of symmetric strategy iteration depending less rigidly on the interplay of the strategies of both players. However, it turns out it has the same shortcomings.
Nfer is a Runtime Verification language for the analysis of event traces that applies rules to create hierarchies of time intervals. This work examines the complexity of the evaluation and satisfiability problems for ...
详细信息
ISBN:
(纸本)9783031742330;9783031742347
Nfer is a Runtime Verification language for the analysis of event traces that applies rules to create hierarchies of time intervals. This work examines the complexity of the evaluation and satisfiability problems for the data-free fragment of nfer. The evaluation problem asks whether a given interval is generated by applying rules to a known input, while the satisfiability problem asks if an input exists that will generate a given interval. By excluding data from the language, we obtain polynomial-time algorithms for the evaluation problem and for satisfiability when only considering inclusive rules. Furthermore, we show decidability for the satisfiability problem for cycle-free specifications and undecidability for satisfiability of full data-free nfer.
We study Lindstrom quantifiers that satisfy certain closure properties which are motivated by the study of polymorphisms in the context of constraint satisfaction problems (CSP). When the algebra of polymorphisms of a...
详细信息
ISBN:
(纸本)9783959773102
We study Lindstrom quantifiers that satisfy certain closure properties which are motivated by the study of polymorphisms in the context of constraint satisfaction problems (CSP). When the algebra of polymorphisms of a finite structure B satisfies certain equations, this gives rise to a natural closure condition on the class of structures that map homomorphically to B. The collection of quantifiers that satisfy closure conditions arising from a fixed set of equations are rather more general than those arising as CSP. For any such conditions P, we define a pebble game that delimits the distinguishing power of the infinitary logic with all quantifiers that are P-closed. We use the pebble game to show that the problem of deciding whether a system of linear equations is solvable in Z /2 Z is not expressible in the infinitary logic with all quantifiers closed under a near-unanimity condition.
暂无评论