Search results for "TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES"
showing 10 items of 174 documents
Operator approach to the Gluing Theorem in String Field Theory
1999
An algebraic proof of the Gluing Theorem at tree level of perturbation theory in String Field Theory is given. Some applications of the theorem to closed string non-polynomial action are briefly discussed
ADT implementation and completion by induction from examples
1991
There exists a fast algorithm [2] for inductive synthesis of terminating and ground confluent term rewriting systems from samples. The principles of this algorithm and the methodology of its use for implementation and completion of abstract data types are described.
Inductive synthesis of term rewriting systems
2005
Fast algorithm for inductive synthesis of term rewriting systems is described and proved to be correct. It is implemented and successfully applied for inductive synthesis of different algorithms, including the binary multiplication. The algorithm proposed supports automatic learning process and can be used for designing and implementation of ADT.
Fuzzy Logic, Knowledge and Natural Language
2012
This is an introductive study on what Fuzzy Logic is, on the difference between Fuzzy Logic and the other many-valued calculi and on the possible relationship between Fuzzy Logic and the complex sciences. Fuzzy Logic is nowadays a very popular logic methodology. Different kinds of applications in cybernetics, in software programming and its growing use in medicine seems to make Fuzzy Logic, according to someone, the “new” logic of science and technology. In his enthusiastic panegyric of Fuzzy Logic, Kosko (1993) argues that after thirty years from the birth of this calculus, it is time to declare the new era of Fuzzy Logic and to forget the old era of classical logic. I think that this poin…
Is recursion language-specific? Evidence of recursive mechanisms in the structure of intentional action
2014
In their 2002 seminal paper Hauser, Chomsky and Fitch hypothesize that recursion is the only human-specific and language-specific mechanism of the faculty of language. While debate focused primarily on the meaning of recursion in the hypothesis and on the human-specific and syntax-specific character of recursion, the present work focuses on the claim that recursion is language-specific. We argue that there are recursive structures in the domain of motor intentionality by way of extending John R. Searle's analysis of intentional action. We then discuss evidence from cognitive science and neuroscience supporting the claim that motor-intentional recursion is language-independent and suggest so…
A fast heuristic for solving the D1EC coloring problem
2010
In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a sub optimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergen…
Building a new CTL model checker using Web services
2013
This Computation Tree Logic (CTL) is widely used to capture compositions of reactive systems. Model checking is particularly well-suited for the automated verification of finite-state systems, both for software and for hardware. A CTL model checker tool allows designers to automatically verify that systems satisfy specifications expressed in the language of CTL logic. In this paper we present a new CTL model checker implemented in client-server paradigm. CTL Designer, the client tool, allows an interactive construction of the CTL models as state-transition graphs. Java and C# APIs are provided for programmatic construction of large models. The server part of our tool embeds the core of the …
Deciding properties of integral relational automata
1994
This paper investigates automated model checking possibilities for CTL* formulae over infinite transition systems represented by relational automata (RA). The general model checking problem for CTL* formulae over RA is shown undecidable, the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL*+, which includes all ”linear time” formulae.
Verification of Well-Formed Communicating Recursive State Machines
2008
AbstractIn this paper we introduce a new (non-Turing equivalent) formal model of recursive concurrent programs called well-formed communicating recursive state machines (CRSM). CRSM extend recursive state machines (RSM) by allowing a restricted form of concurrency: a state of a module can be refined into a finite collection of modules (working in parallel) in a potentially recursive manner. Communication is only possible between the activations of modules invoked on the same fork. We study the model-checking problem of CRSM with respect to specifications expressed in a temporal logic that extends CaRet with a parallel operator (ConCaRet). We propose a decision algorithm that runs in time ex…
ATL model checking in the cloud
2015
This paper gives an overview of our recent work on implementing a new interactive ATL model checker for verification of open systems. In verification based on model checking, we need to provide a model of the system and also write down the properties (ATL formulas) that we require the system to satisfy. Traditionally, the semantics of ATL is given in terms of concurrent game structures. In contrast to previous approaches, our tool permits an interactive design of the ATL models as state-transition graphs, and is based on client/server architecture. The server part, published as Web service in OpenShift cloud platform, embeds the core of the ATL model checker, and the client provides an intu…