Log in

Relevant bibliographies by topics / Parallel satisfiability / Journal articles

To see the other types of publications on this topic, follow the link: Parallel satisfiability.

Journal articles on the topic 'Parallel satisfiability'

Author: Grafiati

Published: 25 May 2024

Last updated: 19 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Parallel satisfiability.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Martins, Ruben, Vasco Manquinho, and Inês Lynce. "Parallel search for maximum satisfiability." AI Communications 25, no. 2 (2012): 75–95. http://dx.doi.org/10.3233/aic-2012-0517.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Martins, Ruben. "Parallel search for maximum satisfiability." Constraints 20, no. 4 (2015): 469–70. http://dx.doi.org/10.1007/s10601-015-9207-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

HAGLIN, DAVID J. "APPROXIMATING MAXIMUM 2-CNF SATISFIABILITY." Parallel Processing Letters 02, no. 02n03 (1992): 181–87. http://dx.doi.org/10.1142/s0129626492000301.

Full text

Abstract:

A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITY problem is presented. This algorithm runs in O( log 2(n + |F|)) parallel time on a CREW PRAM machine using O(n + |F|) processors, where n is the number of variables and |F| is the number of clauses. Performance guarantees are considered for three slightly differing definitions of this problem.

APA, Harvard, Vancouver, ISO, and other styles

4

Feldman, Yulik, Nachum Dershowitz, and Ziyad Hanna. "Parallel Multithreaded Satisfiability Solver: Design and Implementation." Electronic Notes in Theoretical Computer Science 128, no. 3 (2005): 75–90. http://dx.doi.org/10.1016/j.entcs.2004.10.020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

SADOWSKI, Adrian. "A parallel pipelined naive method for testing satisfiability." PRZEGLĄD ELEKTROTECHNICZNY 1, no. 11 (2015): 156–59. http://dx.doi.org/10.15199/48.2015.11.38.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Blochinger, Wolfgang, Carsten Sinz, and Wolfgang Küchlin. "Parallel propositional satisfiability checking with distributed dynamic learning." Parallel Computing 29, no. 7 (2003): 969–94. http://dx.doi.org/10.1016/s0167-8191(03)00068-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Wen-Zhang, Liu, Zhang Jing-Fu, and Long Gui-Lu. "A Parallel Quantum Algorithm for the Satisfiability Problem." Communications in Theoretical Physics 49, no. 3 (2008): 629–30. http://dx.doi.org/10.1088/0253-6102/49/3/22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Cheng, Dan. "The New Democratic Revolution in Music during the Play Experience of the Ideological and Political Education Function." Applied Mechanics and Materials 556-562 (May 2014): 6602–5. http://dx.doi.org/10.4028/www.scientific.net/amm.556-562.6602.

Full text

Abstract:

After a deep investigation on the maximum terms space of the clause set, the concept of the partial maximum terms space of the clause set, which the maximum terms of the clause set decomposed, is brought forward. By investigating the extension rule, this paper introduces the concept of the satisfiability and the unsatisfiability of the partial maximum terms space, and gives an algorithm determining the satisfiability of a partial space of the maximum terms - algorithm PSER (Partial Semi-Extension Rule). Then, the TP problem is decomposed into several sub-problems independent of each other, whi

APA, Harvard, Vancouver, ISO, and other styles

9

HEAD, TOM. "PHOTOCOMPUTING: EXPLORATIONS WITH TRANSPARENCY AND OPACITY." Parallel Processing Letters 17, no. 04 (2007): 339–47. http://dx.doi.org/10.1142/s0129626407003071.

Full text

Abstract:

We continue to search for methods of parallel computing using light. An algorithm for solving instances of the Boolean satisfiability problem is given and illustrated using a photocopying machine with plastic transparencies as medium. The algorithm solves satisfiability problems in linear time but requires the assumption that information can be stored with a density that is exponential in the number of variables in the problem instance. Consideration is given to situations in which this density limitation is not quite absolute.

APA, Harvard, Vancouver, ISO, and other styles

10

Czutro, Alexander, Ilia Polian, Matthew Lewis, Piet Engelke, Sudhakar M. Reddy, and Bernd Becker. "Thread-Parallel Integrated Test Pattern Generator Utilizing Satisfiability Analysis." International Journal of Parallel Programming 38, no. 3-4 (2010): 185–202. http://dx.doi.org/10.1007/s10766-009-0124-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Liao, Xiaojuan, Hui Zhang, Miyuki Koshimura, Rong Huang, Wenxin Yu, and Fagen Li. "Modeling and Solving Scheduling in Overloaded Situations with Weighted Partial MaxSAT." Mathematical Problems in Engineering 2021 (July 16, 2021): 1–17. http://dx.doi.org/10.1155/2021/9615463.

Full text

Abstract:

In real-time systems, where tasks have timing requirements, once the workload exceeds the system’s capacity, missed due dates may cause system overload. In this situation, finding an optimal scheduling that minimizes the cumulative values of late tasks is critical in both theory and practice. Recently, formalizing scheduling problems as a class of generalized problems, such as Satisfiability Modulo Theory (SMT) and Maximum Satisfiability (MaxSAT), has been receiving immense concern. Enlightened by the high efficiency of these satisfiability-based methods, this paper formulates the single-machi

APA, Harvard, Vancouver, ISO, and other styles

12

Huang, Yuexin, Qinzhou Niu, and Yanfang Song. "Research on Abstraction-Based Search Space Partitioning and Solving Satisfiability Problems." Mathematics 13, no. 5 (2025): 868. https://doi.org/10.3390/math13050868.

Full text

Abstract:

Solving satisfiability problems is central to many areas of computer science, including artificial intelligence and optimization. Efficiently solving satisfiability problems requires exploring vast search spaces, where search space partitioning plays a key role in improving solving efficiency. This paper defines search spaces and their partitioning, focusing on the relationship between partitioning strategies and satisfiability problem solving. By introducing an abstraction method for partitioning the search space—distinct from traditional assignment-based approaches—the paper proposes sequent

APA, Harvard, Vancouver, ISO, and other styles

13

Rintanen, Jussi, Keijo Heljanko, and Ilkka Niemelä. "Planning as satisfiability: parallel plans and algorithms for plan search." Artificial Intelligence 170, no. 12-13 (2006): 1031–80. http://dx.doi.org/10.1016/j.artint.2006.08.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Liao, Xiaojuan, Hui Zhang, Miyuki Koshimura, Rong Huang, and Fagen Li. "Solving Restricted Preemptive Scheduling on Parallel Machines with SAT and PMS." JUCS - Journal of Universal Computer Science 29, no. (8) (2023): 911–37. https://doi.org/10.3897/jucs.97743.

Full text

Abstract:

Restricted preemption plays a crucial role in reducing total completion time while controlling preemption overhead. A typical version of restricted preemptive models is <em>k</em>-restricted preemptive scheduling, where preemption is only allowed after a task has been continuously processed for at least <em>k</em> units of time. Though solving this problem of minimizing the makespan on parallel machines is NP-hard in general, it is of vital importance to obtain the optimal solution for small-sized problems, as well as for evaluation of heuristics. This paper proposes optimal strategies to the

APA, Harvard, Vancouver, ISO, and other styles

15

Liao, Xiaojuan, Hui Zhang, Miyuki Koshimura, Rong Huang, and Fagen Li. "Solving Restricted Preemptive Scheduling on Parallel Machines with SAT and PMS." JUCS - Journal of Universal Computer Science 29, no. 8 (2023): 911–37. http://dx.doi.org/10.3897/jucs.97743.

Full text

Abstract:

Restricted preemption plays a crucial role in reducing total completion time while controlling preemption overhead. A typical version of restricted preemptive models is k-restricted preemptive scheduling, where preemption is only allowed after a task has been continuously processed for at least k units of time. Though solving this problem of minimizing the makespan on parallel machines is NP-hard in general, it is of vital importance to obtain the optimal solution for small-sized problems, as well as for evaluation of heuristics. This paper proposes optimal strategies to the aforementioned pro

APA, Harvard, Vancouver, ISO, and other styles

16

Bagchi, Ansuman, Brigitte Servatius, and Weigeng Shi. "2-satisfiability and diagnosing faulty processors in massively parallel computing systems." Discrete Applied Mathematics 60, no. 1-3 (1995): 25–37. http://dx.doi.org/10.1016/0166-218x(94)00041-b.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Lopez Ramirez, Cristina, and Guillermo De Ita Luna. "Modelling the 3-coloring of Serial-Parallel Graphs via Incremental Satisfiability." IEEE Latin America Transactions 17, no. 04 (2019): 607–14. http://dx.doi.org/10.1109/tla.2019.8891885.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Sohn, Andrew. "Parallel Satisfiability Test with Synchronous Simulated Annealing on Distributed-Memory Multiprocessor." Journal of Parallel and Distributed Computing 36, no. 2 (1996): 195–204. http://dx.doi.org/10.1006/jpdc.1996.0100.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Bofill, Miquel, Joan Espasa, and Mateu Villaret. "A Semantic Notion of Interference for Planning Modulo Theories." Proceedings of the International Conference on Automated Planning and Scheduling 26 (March 30, 2016): 56–64. http://dx.doi.org/10.1609/icaps.v26i1.13734.

Full text

Abstract:

The aim of being able to reason about quantities, time, space and much more has been the main objective of the many efforts on the integration of propositional planning with extensions to handle different theories. Planning Modulo Theories (PMT) is an approximation inspired by Satisfiability Modulo Theories (SMT) that generalizes the integration of arbitrary theories with propositional planning. Parallel plans are crucial to reduce plan lengths and hence the time needed to reach a feasible plan in many approaches. Parallelization of actions relies on the notion of (non-)interference, which is

APA, Harvard, Vancouver, ISO, and other styles

20

Martins, Ruben, Vasco Manquinho, and Inês Lynce. "Deterministic Parallel MaxSAT Solving." International Journal on Artificial Intelligence Tools 24, no. 03 (2015): 1550005. http://dx.doi.org/10.1142/s0218213015500050.

Full text

Abstract:

Multicore processors are becoming the dominant platform in modern days. As a result, parallel Maximum Satisfiability (MaxSAT) solvers have been developed to exploit this new architecture. However, parallel MaxSAT solvers suffer from non-deterministic behavior, i.e. several runs of the same solver can lead to different solutions. This is a clear downside for applications that require solving the same problem instance more than once. This paper presents the first deterministic parallel MaxSAT solver that ensures reproducibility of results. Experimental results show that the performance of the ne

APA, Harvard, Vancouver, ISO, and other styles

21

Rankooh, Masood Feyzbakhsh, and Gholamreza Ghassem-Sani. "ITSAT: An Efficient SAT-Based Temporal Planner." Journal of Artificial Intelligence Research 53 (July 30, 2015): 541–632. http://dx.doi.org/10.1613/jair.4697.

Full text

Abstract:

Planning as satisfiability is known as an efficient approach to deal with many types of planning problems. However, this approach has not been competitive with the state-space based methods in temporal planning. This paper describes ITSAT as an efficient SAT-based (satisfiability based) temporal planner capable of temporally expressive planning. The novelty of ITSAT lies in the way it handles temporal constraints of given problems without getting involved in the difficulties of introducing continuous variables into the corresponding satisfiability problems. We also show how, as in SAT-based cl

APA, Harvard, Vancouver, ISO, and other styles

22

Liu, Shengcai, Ke Tang, and Xin Yao. "Automatic Construction of Parallel Portfolios via Explicit Instance Grouping." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1560–67. http://dx.doi.org/10.1609/aaai.v33i01.33011560.

Full text

Abstract:

Exploiting parallelism is becoming more and more important in designing efficient solvers for computationally hard problems. However, manually building parallel solvers typically requires considerable domain knowledge and plenty of human effort. As an alternative, automatic construction of parallel portfolios (ACPP) aims at automatically building effective parallel portfolios based on a given problem instance set and a given rich configuration space. One promising way to solve the ACPP problem is to explicitly group the instances into different subsets and promote a component solver to handle

APA, Harvard, Vancouver, ISO, and other styles

23

Zhang, Kairong, and Masahiro Nagamatu. "Using Attenuation Coefficient Generating Function in Parallel Execution of Neural Networks for Solving SAT." Journal of Advanced Computational Intelligence and Intelligent Informatics 9, no. 2 (2005): 121–26. http://dx.doi.org/10.20965/jaciii.2005.p0121.

Full text

Abstract:

The satisfiability problem (SAT) is one of the most basic and important problems in computer science. We have proposed a recurrent analog neural network called Lagrange Programming neural network with Polarized High-order connections (LPPH) for the SAT, together with a method of parallel execution of LPPH. Experimental results demonstrate a high speedup ratio. Furthermore this method is very easy to realize by hardware. LPPH dynamics has an important parameter, the attenuation coefficient, known to strongly affect LPPH execution speed, but determining a good value of attenuation coefficient is

APA, Harvard, Vancouver, ISO, and other styles

24

Guo, Wensheng, Guowu Yang, Wei Wu, Lei He, and Mingyu Sun. "A Parallel Attractor Finding Algorithm Based on Boolean Satisfiability for Genetic Regulatory Networks." PLoS ONE 9, no. 4 (2014): e94258. http://dx.doi.org/10.1371/journal.pone.0094258.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

ARBELAEZ, ALEJANDRO, CHARLOTTE TRUCHET, and PHILIPPE CODOGNET. "Using sequential runtime distributions for the parallel speedup prediction of SAT local search." Theory and Practice of Logic Programming 13, no. 4-5 (2013): 625–39. http://dx.doi.org/10.1017/s1471068413000392.

Full text

Abstract:

AbstractThis paper presents a detailed analysis of the scalability and parallelization of local search algorithms for the Satisfiability problem. We propose a framework to estimate the parallel performance of a given algorithm by analyzing the runtime behavior of its sequential version. Indeed, by approximating the runtime distribution of the sequential process with statistical methods, the runtime behavior of the parallel process can be predicted by a model based on order statistics. We apply this approach to study the parallel performance of two SAT local search solvers, namely Sparrow and C

APA, Harvard, Vancouver, ISO, and other styles

26

Lück, Martin. "Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic." International Journal of Foundations of Computer Science 29, no. 01 (2018): 17–61. http://dx.doi.org/10.1142/s0129054118500028.

Full text

Abstract:

The satisfiability problem of the branching time logic CTL is studied in terms of computational complexity. Tight upper and lower bounds are provided for each temporal operator fragment. In parallel, the minimal model size is studied with a suitable notion of minimality. Thirdly, flat CTL is investigated, i.e., formulas with very low temporal operator nesting depth. A sharp dichotomy is shown in terms of complexity and minimal models: Temporal depth one has low expressive power, while temporal depth two is equivalent to full CTL.

APA, Harvard, Vancouver, ISO, and other styles

27

Alhazov, Artiom. "Minimal Parallelism and Number of Membrane Polarizations." Triangle, no. 6 (June 28, 2018): 1. http://dx.doi.org/10.17345/triangle6.1-17.

Full text

Abstract:

It is known that the satisfiability problem (SAT) can be efficiently solved by a uniform family of P systems with active membranes that have two polarizations working in a maximally parallel way. We study P systems with active membranes without non-elementary membrane division, working in minimally parallel way. The main question we address is what number of polarizations is sufficient for an efficient computation depending on the types of rules used.In particular, we show that it is enough to have four polarizations, sequential evolution rules changing polarizations, polarizationless non-elem

APA, Harvard, Vancouver, ISO, and other styles

28

Katsirelos, George, Ashish Sabharwal, Horst Samulowitz, and Laurent Simon. "Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (2013): 481–88. http://dx.doi.org/10.1609/aaai.v27i1.8660.

Full text

Abstract:

Recent attempts to create versions of Satisfiability (SAT) solversthat exploit parallel hardware and information sharing have met withlimited success. In fact,the most successful parallel solvers in recent competitions were basedon portfolio approaches with little to no exchange of informationbetween processors. This experience contradicts the apparentparallelizability of exploring a combinatorial search space. Wepresent evidence that this discrepancy can be explained by studyingSAT solvers through a proof complexity lens, as resolution refutationengines. Starting with theobservation that a re

APA, Harvard, Vancouver, ISO, and other styles

29

Song, Bosheng, and Yuan Kong. "Solution to PSPACE-Complete Problem Using P Systems with Active Membranes with Time-Freeness." Mathematical Problems in Engineering 2019 (June 27, 2019): 1–8. http://dx.doi.org/10.1155/2019/5793234.

Full text

Abstract:

P systems with active membranes are powerful parallel natural computing models, which were inspired by cell structure and behavior. Inspired by the parallel processing of biological information and with the idealistic assumption that each rule is completed in exactly one time unit, P systems with active membranes are able to solve computational hard problems in a feasible time. However, an important biological fact in living cells is that the execution time of a biochemical reaction cannot be accurately divided equally and completed in one time unit. In this work, we consider time as an import

APA, Harvard, Vancouver, ISO, and other styles

30

Rybakov, V. "Algorithm for Decision Procedure in Temporal Logic Treating Uncertainty, Plausibility, Knowledge and Interacting Agents." International Journal of Intelligent Information Technologies 6, no. 1 (2010): 31–45. http://dx.doi.org/10.4018/jiit.2010100903.

Full text

Abstract:

Our article studies logic UIALTL, which is a combination of the linear temporal logic LTL, a multi-agent logic with operation for passing knowledge via agents’ interaction, and a suggested logic based on operation of logical uncertainty. The logical operations of UIALTL also include (together with operations from LTL) operations of strong and weak until, agents’ knowledge operations, operation of knowledge via interaction, operation of logical uncertainty, the operations for environmental and global knowledge. UIALTL is defined as a set of all formulas valid at all Kripke-Hintikka like models

APA, Harvard, Vancouver, ISO, and other styles

31

Domshlak, C., J. Hoffmann, and A. Sabharwal. "Friends or Foes? On Planning as Satisfiability and Abstract CNF Encodings." Journal of Artificial Intelligence Research 36 (December 21, 2009): 415–69. http://dx.doi.org/10.1613/jair.2817.

Full text

Abstract:

Planning as satisfiability, as implemented in, for instance, the SATPLAN tool, is a highly competitive method for finding parallel step-optimal plans. A bottleneck in this approach is to *prove the absence* of plans of a certain length. Specifically, if the optimal plan has N steps, then it is typically very costly to prove that there is no plan of length N-1. We pursue the idea of leading this proof within solution length preserving abstractions (over-approximations) of the original planning task. This is promising because the abstraction may have a much smaller state space; related methods a

APA, Harvard, Vancouver, ISO, and other styles

32

Algazy, Kunbolat, Kairat Sakan, Andrey Varennikov, and Nursulu Kapalova. "Application of satisfiability problem solvers for assessing the strength of hash algorithms." International Journal of Electrical and Computer Engineering (IJECE) 15, no. 3 (2025): 3191. https://doi.org/10.11591/ijece.v15i3.pp3191-3201.

Full text

Abstract:

This article presents a methodology for assessing the strength of cryptographic algorithms and provides experimental data obtained from studying the cryptographic strength of the developed hash function HBC-256 using modern satisfiability problem (SAT) solvers. Various SAT solvers implementing the conflict-driven clause learning (CDCL) algorithm, based on the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, were used to conduct the cryptanalysis of the HBC-256 hash function. The most effective was the parallel SAT solver Parkissat, and thus it was used for more in-depth research. A series of e

APA, Harvard, Vancouver, ISO, and other styles

33

Ngoko, Yanik, Christophe Cérin, and Denis Trystram. "Solving Sat in a Distributed Cloud: A Portfolio Approach." International Journal of Applied Mathematics and Computer Science 29, no. 2 (2019): 261–74. http://dx.doi.org/10.2478/amcs-2019-0019.

Full text

Abstract:

Abstract We introduce a new parallel and distributed algorithm for the solution of the satisfiability problem. It is based on an algorithm portfolio and is intended to be used for servicing requests in a distributed cloud. The core of our contribution is the modeling of the optimal resource sharing schedule in parallel executions and the proposition of heuristics for its approximation. For this purpose, we reformulate a computational problem introduced in a prior work. The main assumption is that it is possible to learn optimal resource sharing from traces collected on past executions on a rep

APA, Harvard, Vancouver, ISO, and other styles

34

Богачкова, И. А., О. С. Заикин, С. Е. Кочемазов, И. В. Отпущенников, А. А. Семенов, and О. О. Хамисов. "Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem." Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie), no. 1 (April 2, 2015): 61–77. http://dx.doi.org/10.26089/nummet.v16r107.

Full text

Abstract:

Рассмотрена реализация разностной атаки на криптографические хеш-функции MD4 (Message Digest 4) и MD5 (Message Digest 5) через сведение задачи поиска коллизий для этих хеш-функций к задаче о булевой выполнимости (SAT, SATisfiability). Новизна полученных результатов заключается в том, что предложены существенно более экономные (в сравнении с известными) SAT-кодировки рассматриваемых алгоритмов, а также в использовании для решения полученных SAT-задач современных многопоточных и параллельных SAT-решателей. Задачи поиска одноблоковых коллизий для MD4 в данной постановке оказались чрезвычайно прос

APA, Harvard, Vancouver, ISO, and other styles

35

Ishebabi, Harold, Philipp Mahr, Christophe Bobda, Martin Gebser, and Torsten Schaub. "Answer Set versus Integer Linear Programming for Automatic Synthesis of Multiprocessor Systems from Real-Time Parallel Programs." International Journal of Reconfigurable Computing 2009 (2009): 1–11. http://dx.doi.org/10.1155/2009/863630.

Full text

Abstract:

An automated design approach for multiprocessor systems on FPGAs is presented which customizes architectures for parallel programs by simultaneously solving the problems of task mapping, resource allocation, and scheduling. The latter considers effects of fixed-priority preemptive scheduling in order to guarantee real-time requirements, hence covering a broad spectrum of embedded applications. Being inherently a combinatorial optimization problem, the design space is modeled using linear equations that capture high-level design parameters. A comparison of two methods for solving resulting prob

APA, Harvard, Vancouver, ISO, and other styles

36

Drechsler, Rolf, Görschwin Fey, and Sebastian Kinder. "An integrated approach for combining BDDs and SAT provers." Facta universitatis - series: Electronics and Energetics 20, no. 3 (2007): 415–36. http://dx.doi.org/10.2298/fuee0703415d.

Full text

Abstract:

Many formal verification tools today are based on Boolean proof techniques The two most powerful approaches in this context are Binary Decision Diagrams (BDDs) and methods based on Boolean Satisfiability (SAT). Recent studies have shown that BDDs and SAT are orthogonal, i.e. there exist problems where BDDs work well, while SAT solvers fail and vice versa. Beside this, the techniques are very different in general. E.g. SAT solvers try to find a single solution and BDDs represent all solutions in parallel. In this paper the first integrated approach is presented that combines BDDs and SAT within

APA, Harvard, Vancouver, ISO, and other styles

37

Hao and Liu. "Enhanced Membrane Computing Algorithm for SAT Problems Based on the Splitting Rule." Symmetry 11, no. 11 (2019): 1412. http://dx.doi.org/10.3390/sym11111412.

Full text

Abstract:

Boolean propositional satisfiability (SAT) problem is one of the most widely studied NP-complete problems and plays an outstanding role in many domains. Membrane computing is a branch of natural computing which has been proven to solve NP problems in polynomial time with a parallel compute mode. This paper proposes a new algorithm for SAT problem which combines the traditional membrane computing algorithm of SAT problem with a classic simplification rule, the splitting rule, which can divide a clause set into two axisymmetric subsets, deal with them respectively and simultaneously, and obtain

APA, Harvard, Vancouver, ISO, and other styles

38

INTERLANDI, MATTEO, and LETIZIA TANCA. "A datalog-based computational model for coordination-free, data-parallel systems." Theory and Practice of Logic Programming 18, no. 5-6 (2018): 874–927. http://dx.doi.org/10.1017/s147106841800042x.

Full text

Abstract:

AbstractCloud computingrefers to maximizing efficiency by sharing computational and storage resources, whiledata-parallel systemsexploit the resources available in the cloud to perform parallel transformations over large amounts of data. In the same line, considerable emphasis has been recently given to two apparently disjoint research topics:data-parallel, andeventually consistent, distributedsystems.Declarative networkinghas been recently proposed to ease the task of programming in the cloud, by allowing the programmer to express only the desired result and leave the implementation details t

APA, Harvard, Vancouver, ISO, and other styles

39

Behnke, Gregor, and Susanne Biundo. "X and more Parallelism. Integrating LTL-Next into SAT-based Planning with Trajectory Constraints while Allowing for even more Parallelism." Inteligencia Artificial 21, no. 62 (2018): 75. http://dx.doi.org/10.4114/intartif.vol21iss62pp75-90.

Full text

Abstract:

Linear temporal logic (LTL) provides expressive means to specify temporally extended goals as well as preferences.Recent research has focussed on compilation techniques, i.e., methods to alter the domain ensuring that every solution adheres to the temporally extended goals.This requires either new actions or an construction that is exponential in the size of the formula.A translation into boolean satisfiability (SAT) on the other hand requires neither.So far only one such encoding exists, which is based on the parallel $\exists$-step encoding for classical planning.We show a connection between

APA, Harvard, Vancouver, ISO, and other styles

40

Algazy, Kunbolat, Kairat Sakan, and Nursulu Kapalova. "Evaluation of the strength and performance of a new hashing algorithm based on a block cipher." International Journal of Electrical and Computer Engineering (IJECE) 13, no. 3 (2023): 3124. http://dx.doi.org/10.11591/ijece.v13i3.pp3124-3130.

Full text

Abstract:

The article evaluates the reliability of the new HBC-256 hashing algorithm. To study the cryptographic properties, the algorithm was implemented in software using Python and C programming languages. Also, for the algebraic analysis of the HBC-256 algorithm, a system of Boolean equations was built for one round using the Transalg tool. The program code that implements the hashing algorithm was converted into a software program for generating equations. As a result, one round of the compression function was described as conjunctive normal form (CNF) using 82,533 equations and 16,609 variables. T

APA, Harvard, Vancouver, ISO, and other styles

41

Kunbolat, Algazy, Sakan Kairat, and Kapalova Nursulu. "Evaluation of the strength and performance of a new hashing algorithm based on a block cipher." International Journal of Electrical and Computer Engineering (IJECE) 13, no. 3 (2023): 3124–30. https://doi.org/10.11591/ijece.v13i3.pp3124-3130.

Full text

Abstract:

The article evaluates the reliability of the new HBC-256 hashing algorithm. To study the cryptographic properties, the algorithm was implemented in software using Python and C programming languages. Also, for the algebraic analysis of the HBC-256 algorithm, a system of Boolean equations was built for one round using the Transalg tool. The program code that implements the hashing algorithm was converted into a software program for generating equations. As a result, one round of the compression function was described as conjunctive normal form (CNF) using 82,533 equations and 16,609 variables. T

APA, Harvard, Vancouver, ISO, and other styles

42

Shi, Kai, Huiqun Yu, Jianmei Guo, Guisheng Fan, Liqiong Chen, and Xingguang Yang. "A Parallel Framework of Combining Satisfiability Modulo Theory with Indicator-Based Evolutionary Algorithm for Configuring Large and Real Software Product Lines." International Journal of Software Engineering and Knowledge Engineering 29, no. 04 (2019): 489–513. http://dx.doi.org/10.1142/s0218194019500219.

Full text

Abstract:

Multi-objective evolutionary algorithm (MOEA) has been widely applied to software product lines (SPLs) for addressing the configuration optimization problems. For example, the state-of-the-art SMTIBEA algorithm extends the constraint expressiveness and supports richer constraints to better address these problems. However, it just works better than the competitor for four out of five SPLs in five objectives and the convergence speed is not significantly increased for largest Linux SPL from 5 to 30[Formula: see text]min. To further improve the optimization efficiency, we propose a parallel frame

APA, Harvard, Vancouver, ISO, and other styles

43

Minaeva, Anna, and Zdeněk Hanzálek. "Survey on Periodic Scheduling for Time-triggered Hard Real-time Systems." ACM Computing Surveys 54, no. 1 (2021): 1–32. http://dx.doi.org/10.1145/3431232.

Full text

Abstract:

This survey covers the basic principles and related works addressing the time-triggered scheduling of periodic tasks with deadlines. The wide range of applications and the increasing complexity of modern real-time systems result in the continually growing interest in this topic. However, the articles in this field appear without systematic notation. To address it, we extend the three-field Graham notation to cover periodic scheduling. Moreover, we formally define three example periodic scheduling problems (PSPs) and provide straightforward implementations of these examples in the Satisfiabilit

APA, Harvard, Vancouver, ISO, and other styles

44

Guo, Mengyu. "A Review of Research on Algorithms for Solving SAT Problems." Mathematical Modeling and Algorithm Application 2, no. 1 (2024): 6–10. http://dx.doi.org/10.54097/1mn6v127.

Full text

Abstract:

The SAT problem solving algorithms are an important research area in computer science aimed at solving the Boolean satisfiability problem. With the wide application of SAT problems in the fields of hardware design, automated planning, and artificial intelligence, researchers have proposed a variety of efficient solution algorithms. The classical algorithms include exhaustive search and backtracking search, but they are less efficient when dealing with large-scale problems. Heuristic search methods accelerate the search process by introducing randomization or evolutionary algorithms to improve

APA, Harvard, Vancouver, ISO, and other styles

45

HOOS, HOLGER, ROLAND KAMINSKI, MARIUS LINDAUER, and TORSTEN SCHAUB. "aspeed: Solver scheduling via answer set programming." Theory and Practice of Logic Programming 15, no. 1 (2014): 117–42. http://dx.doi.org/10.1017/s1471068414000015.

Full text

Abstract:

AbstractAlthough Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is known to depend strongly on algorithm parameters. This problem was addressed by means of a simple, yet effective approach using handmade, uniform, and unordered schedules of multiple solvers inppfolio, which showed very impressive performance in the 2011 Satisfiability Testing (SAT) Competition. Inspired by this, we take advantage of the modeling and solving capacities of Answ

APA, Harvard, Vancouver, ISO, and other styles

46

López, Rodrigo, Roberto Asín-Achá, and Jorge A. Baier. "A New Upper Bound for the Makespan of Cost-Optimal Solutions for Multi-Agent Path Finding (Extended Abstract)." Proceedings of the International Symposium on Combinatorial Search 17 (June 1, 2024): 275–76. http://dx.doi.org/10.1609/socs.v17i1.31578.

Full text

Abstract:

A well-known approach to solving Multi-Agent Path Finding (MAPF) optimally is compilation to Boolean Satisfiability or Answer Set Programming (ASP). Such compilation-based approaches are superior to other approaches on dense, relatively small instances and may invoke the solver multiple times, each with an encoding of the same instance for a different makespan. Critical to their performance is the runtime of the last solver invocation, whose input is the instance encoded with a theoretical upper bound of the makespan of the optimal solution. In this paper, we propose a new theoretical upper bo

APA, Harvard, Vancouver, ISO, and other styles

47

Muniyandi, Ravie Chandren, and Ali Maroosi. "A Representation of Membrane Computing with a Clustering Algorithm on the Graphical Processing Unit." Processes 8, no. 9 (2020): 1199. http://dx.doi.org/10.3390/pr8091199.

Full text

Abstract:

Long-timescale simulations of biological processes such as photosynthesis or attempts to solve NP-hard problems such as traveling salesman, knapsack, Hamiltonian path, and satisfiability using membrane systems without appropriate parallelization can take hours or days. Graphics processing units (GPU) deliver an immensely parallel mechanism to compute general-purpose computations. Previous studies mapped one membrane to one thread block on GPU. This is disadvantageous given that when the quantity of objects for each membrane is small, the quantity of active thread will also be small, thereby de

APA, Harvard, Vancouver, ISO, and other styles

48

Tan, Daniel Bochen, Dolev Bluvstein, Mikhail D. Lukin, and Jason Cong. "Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors." Quantum 8 (March 14, 2024): 1281. http://dx.doi.org/10.22331/q-2024-03-14-1281.

Full text

Abstract:

Dynamically field-programmable qubit arrays (DPQA) have recently emerged as a promising platform for quantum information processing. In DPQA, atomic qubits are selectively loaded into arrays of optical traps that can be reconfigured during the computation itself. Leveraging qubit transport and parallel, entangling quantum operations, different pairs of qubits, even those initially far away, can be entangled at different stages of the quantum program execution. Such reconfigurability and non-local connectivity present new challenges for compilation, especially in the layout synthesis step which

APA, Harvard, Vancouver, ISO, and other styles

49

Gütl, Christian. "Editorial." JUCS - Journal of Universal Computer Science 29, no. (8) (2023): 836–37. https://doi.org/10.3897/jucs.109658.

Full text

Abstract:

Dear Readers, It gives me great pleasure to announce the eighth regular issue of 2023. In this issue, five papers by 24 authors from nine countries cover various topical aspects of computer science. In an ongoing effort to further strengthen our journal, I would like to expand the editorial board: If you are a tenured associate professor or above with a strong publication record, you are welcome to apply to join our editorial board. We are also interested in high-quality proposals for special issues on new topics and trends. As always, I would like to thank all the authors for their sound rese

APA, Harvard, Vancouver, ISO, and other styles

50

Gütl, Christian. "Editorial." JUCS - Journal of Universal Computer Science 29, no. 8 (2023): 836–37. http://dx.doi.org/10.3897/jucs.109658.

Full text

Abstract:

Dear Readers,&nbsp; It gives me great pleasure to announce the eighth regular issue of 2023. In this issue, five papers by 24 authors from nine countries cover various topical aspects of computer science. In an ongoing effort to further strengthen our journal, I would like to expand the editorial board: If you are a tenured associate professor or above with a strong publication record, you are welcome to apply to join our editorial board. We are also interested in high-quality proposals for special issues on new topics and trends.&nbsp; As always, I would like to thank all the authors

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!