On the concepts of problem and problem-solving method

The concepts of problem, problem-solving method, and the application of a problem-solving method to a problem are given precise formulations, based on abstract data types. These formulations are argued to agree with the intuitive understanding of these ideas, thereby formalizing them. This formalization is based on few basic concepts: abstract data type and an extension mechanism (here, a general cluster-like module). Moreover, by embodying ideas related to stepwise refinement they are applicable both to problem solving in general and to the process of program development. Examples are provided to illustrate the main ideas and their application.     

Cybersecurity policy verification with declarative programming

Cybersecurity is a growing concern in today’s society. Security policies have been developed to ensure that data and assets remain protected for legitimate users, but there must be a mechanism to verify that these policies can be enforced. This paper addresses the verification problem of security policies in role-based access control of enterprise software. Most existing approaches employ traditional logic or procedural programming that tends to involve complex expressions or search with backtrack. These can be time-consuming, and hard to understand, and update, especially for large-scale security verification problems. Declarative programming paradigms such as “Answer Set” programming have been widely used to alleviate these issues by ways of elegant and flexible modeling for complex search problems. However, solving problems using these paradigms can be challenging due to the nature and limitation of the declarative problem solver. This paper presents an approach to automated security policy verification using Answer Set programming. In particular, we investigate how the separation of duty security policy in role-based access control can be verified. Our contribution is a modeling approach that maps this verification problem into a graph-coloring problem to facilitate the use of generate-and-test in a declarative problem-solving paradigm. The paper describes a representation model and rules that drive the Answer Set Solver and illustrates the proposed approach to securing web application software to assist the hiring process in a company.     

Guest Editors' Introduction: Planning with Templates

Templates are standard operating procedures that can be used for solving typical problems and as a starting point for solving novel problems. These structures contain relevant variables (and required activities) and current variable values (or specific activities) that affect a problem or have been chosen in a problem-solving instance. With templates you can configure domain-independent planning algorithms, making them applicable to many different problem domains. By making the template explicit for the user in the form of a GUI, you can facilitate mixed-initiative, user-centric systems that help maintain awareness of complex and dynamic situations, share information across the network, and solve problems incrementally and iteratively.     

Program families: Program construction by context independent refinements

The concept of program families is a generalisation of the conventional stepwise refinement paradigm. We formalise program families by allowing Hoare-triplets to be parameterized. Next we derive a simple calculus to develop programs which are known a priori to be correct with respect to explicitly formulated pre- and postconditions.

Program families deal with at least two important problems of conventional refinement steps, i.e. program families are not context dependent and they apply just as well to top-down decomposition as to the bottom-up or middle-out approach. It turns out that the meaning of a pseudostatement in the context of program families is quite different from its meaning in the conventional refinement process.

A couple of examples illustrate the technique: the 1000 primes problem, a palindrome filter and a sorting routine.

The discussion relates program families to Morgan's refinement calculus, Knuth' literate programming and Soloway's programming plans.     

The Paradigm Shift Process

The quality movement has generated a proliferation of philosophies and approaches to quality practices and techniques. Once businesses successfully solved some of their problems using one of these methods, they would use this method of solving problems as the new model for solving other problems. This ‘paradigm’ then became their model for how to be successful. The word ‘paradigm’ comes from the Greek word paradeigma, meaning model, pattern or example. Management is currently very interested in their existing paradigms. However, a new pattern is beginning to emerge. Companies are finding that their efforts to generate significant results have fallen short of expectation and they now see themselves as having hit a ‘plateau’. These companies are now searching for the next step in moving their business to higher levels. Paradigm shifts can represent leaps of significant change to organizations and may be the necessary ‘next step’ in keeping businesses successful. A paradigm shift process offers an applied approach to making changes as an individual or an organization to move beyond existing paradigms.     

Acquiring and representing strategic knowledge in the diagnosis domain

Abstract: Techniques for acquiring and representing strategic knowledge for guiding diagnostic processes are presented. In a diagnostic expert system, strategic knowledge can be represented either by a specific knowledge base or it can be 'embedded' into the inference engine. We decided for the former; so that knowledge can be acquired or modified without affecting the problem solving paradigm. Strategic knowledge is acquired by expert interview in a straightforward way: on the basis of simple information provided by the expert, an internal sophisticated representation is automatically generated. The techniques are not restricted to a particular problem-solving paradigm or application. However, in order to prove the effectiveness of our approach, a problem solving paradigm is also presented. The paradigms adopted in diagnosis must face two problems: the selection of the 'right' hypothesis (fault) to pursue and the selection of the 'right' observation (measurement) to be executed. We present some criteria for selecting hypotheses and observations. Our proposal is suitable for domains where the measurements to localise the fault do not always provide certainty but only a 'degree of belief' about the presence of the fault. As a consequence, the problem of selecting the right measurement is solved by appropriate criteria and heuristic reasoning. Moreover, we do not consider 'right' as a predefined concept: actually, it is based on the information provided by the expert. So he can define this concept on the basis of his own judgment.     

Operational versus definitional: a perspective on programming paradigms

Various paradigms that support high-level programming are discussed independently of supporting languages. The paradigms are grouped according to their approach to problem solving. The operational approach describes step-by-step how to construct a solution. The demonstrational approach is a variation on it that illustrates the solution operationally for specific examples and lets the system generalize these example solutions for other cases. The definitional approach is different. It states properties about the solution to constrain it without describing how to compute it. These three approaches are viewed on a continuum from operational to definitional. A pure language solution to the problem of sorting a list into some linear order is presented for each paradigm.<>     

Stepwise refinement revisited

In this paper, rigorous application of stepwise refinement is explored. The steps of definition, decomposition, and completion are described, where completion is a newly introduced step. This combination of steps extends the use of stepwise refinement to larger systems. The notions of range, active objects, and backlog interface are introduced. Verification of incomplete programs via interactive testing is described. The paradigm is demonstrated in an example. The relationship between the paradigm and the current programming languages is considered. It is argued that the WHILE-DO loop is a harmful construct from this point of view.     

Learning to Improve Coordinated Actions in Cooperative Distributed Problem-Solving Environments

Coordination is an essential technique in cooperative, distributed multiagent systems. However, sophisticated coordination strategies are not always cost-effective in all problem-solving situations. This paper presents a learning method to identify what information will improve coordination in specific problem-solving situations. Learning is accomplished by recording and analyzing traces of inferences after problem solving. The analysis identifies situations where inappropriate coordination strategies caused redundant activities, or the lack of timely execution of important activities, thus degrading system performance. To remedy this problem, situation-specific control rules are created which acquire additional nonlocal information about activities in the agent networks and then select another plan or another scheduling strategy. Examples from a real distributed problem-solving application involving diagnosis of a local area network are described.     

Beyond Simon’s Means-Ends Analysis: Natural Creativity and the Unanswered ‘Why’ in the Design of Intelligent Systems for Problem-Solving

Goal-directed problem solving as originally advocated by Herbert Simon’s means-ends analysis model has primarily shaped the course of design research on artificially intelligent systems for problem-solving. We contend that there is a definite disregard of a key phase within the overall design process that in fact logically precedes the actual problem solving phase. While systems designers have traditionally been obsessed with goal-directed problem solving, the basic determinants of the ultimate desired goal state still remain to be fully understood or categorically defined. We propose a rational framework built on a set of logically inter-connected conjectures to specifically recognize this neglected phase in the overall design process of intelligent systems for practical problem-solving applications.     

A model-driven approach to building modern Semantic Web-Based User Interfaces

The Semantic Web has widely spread in the last 10 years as a suitable web platform to support semantics and expressive information seeking. However, one of the main problems with this paradigm is still the representation and manipulation of ontologies as well as the complex relationships that they implicitly represent. Actually, this remains a challenge when unskilled users have to deal with this abstract representation in order to carry out daily solving-problem activities (e.g., designing web applications based on ontologies). This probably made the Semantic Web to decrease in popularity, also being commercially unsupported and overcame by recent technologies and services based on the Web 2.0, the emerging end-user-focused web concept. All in all, the specification of Model-Based User Interfaces fits very well to both paradigms. Accordingly, the aim of this work is to provide new ways of modeling user interfaces based on semantic models that better fit the domain problem. At the same time, we think of exploiting interactive features through current and modern end-user programming elements based on the Web 2.0, finally contributing to an architecture that supports higher interactive end-user interfaces on the web.     

Sign use and cognition in automated scientific discovery: are computers only special kinds of signs?

James Fetzer criticizes the computational paradigm, prevailing in cognitive science by questioning, what he takes to be, its most elementary ingredient: that cognition is computation across representations. He argues that if cognition is taken to be a purposive, meaningful, algorithmic problem solving activity, then computers are incapable of cognition. Instead, they appear to be signs of a special kind, that can facilitate computation. He proposes the conception of minds as semiotic systems as an alternative paradigm for understanding mental phenomena, one that seems to overcome the difficulties of computationalism. Now, I argue, that with computer systems dealing with scientific discovery, the matter is not so simple as that. The alleged superiority of humans using signs to stand for something other over computers being merely “physical symbol systems” or “automatic formal systems” is only easy to establish in everyday life, but becomes far from obvious when scientific discovery is at stake. In science, as opposed to everyday life, the meaning of symbols is, apart from very low-level experimental investigations, defined implicitly by the way the symbols are used in explanatory theories or experimental laws relevant to the field, and in consequence, human and machine discoverers are much more on a par. Moreover, the great practical success of the genetic programming method and recent attempts to apply it to automatic generation of cognitive theories seem to show, that computer systems are capable of very efficient problem solving activity in science, which is neither purposive nor meaningful, nor algorithmic. This, I think, undermines Fetzer’s argument that computer systems are incapable of cognition because computation across representations is bound to be a purposive, meaningful, algorithmic problem solving activity.     

Factors of problem-solving competency in a virtual chemistry environment: The role of metacognitive knowledge about strategies

The ability to solve complex scientific problems is regarded as one of the key competencies in science education. Until now, research on problem solving focused on the relationship between analytical and complex problem solving, but rarely took into account the structure of problem-solving processes and metacognitive aspects. This paper, therefore, presents a theoretical framework, which describes the relationship between the components of problem solving and strategy knowledge.In order to assess the constructs, we developed a virtual environment which allows students to solve interactive and static problems. 162 students of grade 10 and the upper secondary level completed the tests within a cross-sectional survey. In order to investigate the structure of problem-solving competency, we established measurement models representing different theoretical assumptions, and evaluated model fit statistics by using confirmatory factor analyses.Results show that problem-solving competency in virtual environments comprises to three correlated abilities: achieving a goal state, systematical handling of variables, and solving analytical tasks. Furthermore, our study provides empirical evidence on the distinction between analytical and complex problem solving.Additionally, we found significant differences between students of grades 10 and 12 within the problem-solving subscales, which could be explained by gaming experience and prior knowledge. These findings are discussed from a measurement perspective. Implications for assessing complex problem solving are given.     

Transitional feedback schedules during computer-based problem-solving practice

Feedback has a strong influence on effective learning from computer-based instruction. Prior research on feedback in computer-based instruction has mainly focused on static feedback schedules that employ the same feedback schedule throughout an instructional session. This study examined transitional feedback schedules in computer-based multimedia instruction on procedural problem-solving in electrical circuit analysis. Specifically, we compared two transitional feedback schedules: the TFS-P schedule switched from initial feedback after each problem step to feedback after a complete problem at later learning states; the TFP-S schedule transitioned from feedback after a complete problem to feedback after each problem step. As control conditions, we also considered two static feedback schedules, namely providing feedback after each practice problem-solving step (SFS) or providing feedback after attempting a complete multi-step practice problem (SFP). Results indicate that the static stepwise (SFS) and transitional stepwise to problem (TFS-P) feedback produce higher problem solving near-transfer post-test performance than static problem (SFP) and transitional problem to step (TFP-S) feedback. Also, TFS-P resulted in higher ratings of program liking and feedback helpfulness than TFP-S. Overall, the study results indicate benefits of maintaining high feedback frequency (SFS) and reducing feedback frequency (TFS-P) compared to low feedback frequency (SFP) or increasing feedback frequency (TFP-S) as novice learners acquire engineering problem solving skills.     

Learning adaptation knowledge to improve case-based reasoning

Case-Based Reasoning systems retrieve and reuse solutions for previously solved problems that have been encountered and remembered as cases. In some domains, particularly where the problem solving is a classification task, the retrieved solution can be reused directly. But for design tasks it is common for the retrieved solution to be regarded as an initial solution that should be refined to reflect the differences between the new and retrieved problems. The acquisition of adaptation knowledge to achieve this refinement can be demanding, despite the fact that the knowledge source of stored cases captures a substantial part of the problem-solving expertise. This paper describes an introspective learning approach where the case knowledge itself provides a source from which training data for the adaptation task can be assembled. Different learning algorithms are explored and the effect of the learned adaptations is demonstrated for a demanding component-based pharmaceutical design task, tablet formulation. The evaluation highlights the incremental nature of adaptation as a further reasoning step after nearest-neighbour retrieval. A new property-based classification to adapt symbolic values is proposed, and an ensemble of these property-based adaptation classifiers has been particularly successful for the most difficult of the symbolic adaptation tasks in tablet formulation.     

Computer-assisted learning for mathematical problem solving

Previous computer-assisted problem-solving systems have incorporated all the problem-solving steps within a single stage, making it difficult to diagnose stages at which errors occurred when a student encounters difficulties, and imposing a too-high cognitive load on students in their problem solving. This study proposes a computer-assisted system named MathCAL, whose design is based on four problem-solving stages: (1) understanding the problem, (2) making a plan, (3) executing the plan and (4) reviewing the solution. A sample of one hundred and thirty fifth-grade students (aged 11 years old) completed a range of elementary school mathematical problems and empirically demonstrated. The results showed MathCAL to be effective in improving the performance of students with lower problem solving ability. This evaluation allowed us to address the problem of whether the assistances in various stages help students with their problem solving. These assistances improve students’ problem-solving skills in each stage.     

GENETICA: A computer language that supports general formal expression with evolving data structures

This paper presents a general problem-solving method combining the principles of artificial intelligence and evolutionary computation. The problem-solving method is based on the computer language GENETICA, which stands for "Genetic Evolution of Novel Entities Through the Interpretation of Composite Abstractions." GENETICAs programming environment includes a computational system that evolves data abstractions, viewed as genotypes of data generation scenarios for a GENETICA program, with respect to either confirmation or optimization goals. A problem can be formulated as a GENETICA program, while the solution is represented as a data structure resulting from an evolved data generation scenario. This approach to problem solving offers: 1) generality, since it concerns virtually any problem stated in formal logic; 2) effectiveness, since formally expressed problem-solving knowledge can be incorporated in the problem statement; and 3) creativity, since unpredictable solutions can be obtained by evolved data structures. It is shown that domain specific languages, including genetic programming ones, that inherit GENETICAs features can be developed in GENETICA. The language G-CAD, specialized to problem solving in the domain of architectural design, is presented as a case study followed by experimental results.