bluuebunny/crossref_metadata_2025 huggingface dataset:
Dietary Supplementation of Fructooligosaccharides Reduces Hepatic Steatosis Associated with Insulin Resistance in Obese Zucker Rats
Authors: Kaume Lydia , Gilbert William , Gadang Vidya , Devareddy Latha
Published: December 2019

Background: One in five adults in the United States is obese as defined by a body mass index of 30 kg/m2. Obesity is associated with metabolic syndrome, a combination of medical conditions including cardiovascular disease, type 2 diabetes, hypertension, hypercholesterolemia, and hypertriglyceridemia. These conditions present challenges to the medical care system and require a multifaceted approach through a variety of interventions. This study investigated the effects of fructooligosaccharides (FOS) at the level of 5 % (w/w) in alleviating the complications associated with metabolic syndrome.Methods: The study was carried out using thirty-six, three-month old female lean and obese Zucker rats housed in an environmentally controlled laboratory. The Zucker rats were divided into three groups (N=12): Lean (L-CTRL) and obese controls (O-CTRL) and obese-FOS (O-FOS). The controls received AIN-93M purified rodent diet and the animals in the O-FOS group were fed AIN-93M diet modified to contain 5.0% FOS (w/w). After 100 days of treatment, the rats were fasted for 12 hours and sacrificed. Tissue and organs of interest, and blood were collected for analysis. Serum concentrations of the following were determined: glucose, glycosylated hemoglobin (HbA1c), total cholesterol (TC), low-density lipoprotein-cholesterol (LDL-C), high-density lipoprotein-cholesterol (HDL-C), triglycerides (TG), and insulin. Gravimetric quantification of liver lipids was performed and peroxisome proliferator-activated receptor-γ (PPAR-γ) gene expression was determined in white adipose tissue by qRT-PCR.Results: No significant differences were observed in the serum lipids, fasting blood glucose, HbA1c and PPAR-γ gene expression in white adipose tissue of O-FOS group compared to O-CTRL group. FOS supplementation significantly lowered the percent total liver lipids by 12% with a subsequent reduction in the liver weights compared to O-CTRL rats. Serum insulin concentrations were lowered 3.6 fold in O-FOS group compared to O-CTRL (P < 0.05). Conclusion: Based on these findings we conclude that dietary supplementation of 5% FOS (w/w) may reduce hepatic steatosis and the risk for non-alcoholic fatty liver disease (NAFLD) associated with insulin resistance without changes in blood lipids and glucose levels.Key words: Dietary fiber, Fructooligosaccharide, Hepatosteatosis, Liver lipids, Non-alcoholic fatty liver disease (NAFLD), Zucker.
Antioxidant Activity and Mechanism of Protocatechuic Acid in vitro
Authors: Li Xican , Wang Xiaozhen , Chen Dongfeng , Chen Shuzhi
Published: December 2019

Background: Protocatechuic acid (PCA) is a natural phenolic acid widely distributed in plants and is considered as an active component of some traditional Chinese herbal medicines such as Cibotium barometz (L.) J.Sm, Stenoloma chusanum (L.) Ching, Ilex chinensis Sims. PCA was reported to possess various pharmacological effects which may be closely correlated with its antioxidant activities. However, the antioxidant of PCA has not been investigated systematically yet. Methods: In the study, the antioxidant activities of protocatechuic acid were measured in vitro using various antioxidant assays including 1,1-diphenyl-2-picryl-hydrazyl (DPPH•), 2,2’-azino-bis (3-ethylbenzthiazoline-6-sulfonic acid) (ABTS+•), superoxide anion radicals (•O2-) and hydroxyl radical (•OH) scavenging activity, ferric ions (Fe3+) and cupric ions (Cu2+) reducing power, ferrous ions (Fe2+) and cupric ions (Cu2+) chelating activity, compared with the positive controls Trolox or BHT.Results: In all assays, PCA along with positive controls exhibited dose-dependently antioxidant ability. Comparing to a standard antioxidant Trolox, the relative antioxidant activity of PCA (i.e. the ratio of IC50(Trolox)/IC50(PCA) ) was calculated as 2.8, 2.3, 3.7, 6.1, 4.2, 1.0, 2.7, 1.5, respectively, for DPPH, ABTS, reducing power (Fe3+), reducing power (Cu2+), superoxide anion radical-scavenging, hydroxyl radical-scavenging, chelating ability (Fe2+) and chelating ability (Cu2+). Conclusion: Comparing to Trolox, PCA shows much more effective antioxidant activity in vitro in both lipid and aqueous media. Hence, it could therefore be used in pharmacological or food industry as a natural antioxidant. It may exhibit antioxidant activity by both chelating metal transition ions as well as by scavenging free radicals via donating hydrogen atom (H•) or electron (e).Keywords: Protocatechuic acid, antioxidant, reducing power, free radical-scavenging, chelating ability.
Randomized, double-blind, placebo-controlled, crossover study to evaluate the effects of beta-1,3/1,6 glucan on stress associated with daily lifestyle in healthy subjects
Authors: Ojiri Yoshihiko , Endoh Hiroshi , Okumoto Tadashi , Atsuta Kazushi , Yoshinari Orie , Moriyama Hiroyoshi
Published: December 2019

Background: Fatigue is attributable to physical and psychological stress. Fatigue is also a common symptom which occurs in both sick and healthy individuals. Although its mechanism of cause is complex, fatigue from stress is known to affect the existing equilibrium of the immune system. However, nutrition, such as beta-1,3/1,6 glucan, has been reported to play an important role in regulating stress and fatigue states, via modulating a weakened immune system. In this study, a popular and healthy beverage in Okinawa, Japan, containing a soluble baker’s yeast in black koji vinegar (Moromisu), was provided to healthy subjects with a non-strenuous daily lifestyle.Results: By performing statistical analysis on the results of the Profile of Mood States (POMS) survey, we observed that overall study results (n=14) demonstrated significant differences in fatigue and confusion in the POMS factors.Conclusions: In this study we confirmed that beta-1,3/1,6 glucan improved some of the factors related to stress and fatigue, as indicated by evaluation of POMS survey results.Key Words: Beta-1,3/1,6-glucan, vinegar, POMS, stress
Flüchtige Präsenz. Umkämpfte Solidaritäten des EU-Migrationsregimes
Authors: Gebhardt Mareike
Published: December 2019

Der Beitrag diskutiert das Migrationsregime der EU im Hinblick auf ambivalente Prozesse der (Ent-)Solidarisierung. Er betrachtet zunächst Bewegungen der binneneuropäischen Entsolidarisierung, die durch die strukturellen Asymmetrien der Dublin-Verordnungen evoziert werden. Fokussiert wird dabei der Nord-Süd-Konflikt zwischen Italien und der EU, in dem neo-koloniale Differenzen zwischen den ‚Kernstaaten‘ und den südlichen ‚Peripherien‘ Europas reproduziert werden. Im Folgenden konzentriert sich die Untersuchung dann auf eine radikaldemokratietheoretische Analyse der Proteste von „Lampedusa in Hamburg“, anhand derer europäische Solidarisierungsbewegungen aufgezeigt werden. Im Anschluss an die Arbeiten von Judith Butler, Isabell Lorey und Jacques Rancière wird hierfür das Konzept der flüchtigen Präsenz entwickelt, durch das die Proteste von „Lampedusa in Hamburg“ als widerständige Subjektivierung lesbar werden.
Feministische Solidarität als Kosmopolitik
Authors: Leinius Johanna
Published: December 2019

In meinem Beitrag diskutiere ich, inwiefern die Anerkennung von Differenz als Basis für feministische Solidarität dienen kann. Ich verbinde die Debatten innerhalb postkolonial-feministischer Theorie über die Un/Möglichkeiten von feministischer Solidarität mit der Perspektive der Politischen Ontologie, um Kosmopolitik als die Verhandlungen zwischen miteinander in ungleicher Beziehung verbundener heterogener Welten zu greifen. Dafür untersuche ich zwei Bewegungstreffen in Peru, die Fünften Dialogen zwischen Bewegungen und Wissen sowie das 13. Feministische Lateinamerikanische und Karibische Treffen. Um zu analysieren, wie Differenz auf den beiden Treffen konstruiert wird und welche Effekte dies auf die Möglichkeit hat, Solidarität zu praktizieren, schlage ich zwei Konstellationen von Solidarität und Kosmopolitik vor: Kosmopolitische Solidarität bezeichnet eine Haltung gegenüber als different betrachteten Gruppen und Individuen, die Differenz als Stärke emanzipatorischer Kämpfe sieht. Statt exklusive Grenzen zu betonen, wird die Intersektionalität verschiedener Kämpfe anerkannt, das geteilte politische Bewusstsein wird als erst im gemeinsamen Kampf geschaffen gesehen, und die Praxis der Imagination wird eingesetzt, um potenzielle Inkommensurabilitäten zu überbrücken. Kosmopolitik der Solidarität meint hingegen die Praxen der Solidarität, die heterogene und potenziell nicht ineinander aufgehende Kämpfe verschränken und auf wechselseitiger Kritik aufbauen. Erst die gemeinsame Betrachtung beider Konstellationen, so mein Argument, kann die machtvollen Aushandlungsprozesse fassen, die feministische Solidarität als dekolonisierende Praxis ermöglichen.
ON THE CHARACTERIZATION OF INPUT SETS AS OUTPUT SETS
Authors: Skandalis Kostas
Published: December 2019

In [1] it is proved that for real closed fields the output sets (of computing machines) are also input sets. In this work it is shown that the converse holds for a class of ordered fields. It follows that the uncountable subfields of R are real closed if and only if their output sets are also input sets. Similar results for unordered fields of characteristic 0 are obtained.
ON THE GENERATIVE CAPACITY OF CERTAIN CLASSES OF COOPERATING GRAMMAR SYSTEMS
Authors: Dassow Jürgen , Paun Gheorghe , Vicolov Sorina
Published: December 2019

The paper looks for necessary conditions for a language to be generated by a cooperating distributed grammar system with modes = k and ≥ k of derivation. It is proved that the length set of such languages contains infinite arithmetical progressions. Some consequences of this result are derived, concerning the power of these grammars and the closure properties of the corresponding families. Then, one proves that these systems can generate non-semi-linear languages. (Both these questions were formulated as open problems in the field literature.)
GRAMMATICAL CODES OF TREES AND TERMINALLY CODED GRAMMARS
Authors: Ehrenfeucht Andrzej , Engelfriet Joost , Pas Paulien ten , Rozenberg Grzegorz
Published: December 2019

We introduce terminally coded (TC) grammars, which generalize parenthesis grammars in the sense that from each word ω generated by a TC grammar we can recover the unlabeled tree t underlying its derivation tree(s). More precisely, there is a length-preserving homomorphism that maps ω to an encoding of t. Basic properties of TC grammars are established. For backwards deterministic TC grammars we give a shift-reduce precedence parsing method without look-ahead, which implies that TC languages can be recognized in linear time. The class of TC languages contains all parenthesis languages, and is contained in the classes of simple precedence languages and NTS languages.
A DEFAULT LOGIC BASED ON EPISTEMIC STATES
Authors: Ch. Meyer J.-J. , van der Hoek W.
Published: December 2019

In this paper we indicate how default logic can be based on epistemic logic, and particularly how we may employ Halpern & Moses' minimal epistemic states for this purpose. In this way we obtain a simple and natural S5-based logic for default reasoning that appears to be cumulative in the sense of Kraus, Lehmann and Magidor.
RELATIONAL ALGEBRA AND EQUATIONAL PROOFS
Authors: de Kogel Eric
Published: December 2019

A proposal is made for a formal framework in which equational provability can be represented and investigated. The basic formalism is an algebra of binary relations on ground terms of a first-order language. Two special-purpose mappings are introduced to deal with the structure of terms. Equational provability is characterized in terms of least fixpoints of some mappings. The use of the relational framework is illustrated by a few examples. It is shown that provability of an equation from a finite set of equations, where all equations are variable-free, is decidable. Then we discuss a method by Reeves ([3]) to deal with equations in semantic tableaux, that we can now prove to be complete in a very simple way. Finally, we discuss an equational proof format that is naturally induced by the relational formulation and serves as a guideline in finding proofs. The relation between Reeves' rules and the construction of such proofs is made explicit.
APPROXIMATE INFERENCE IN DEFAULT LOGIC AND CIRCUMSCRIPTION
Authors: Cadoli Marco , Schaerf Marco
Published: December 2019

We propose a technique for dealing with the high complexity of reasoning under propositional default logic and circumscription. The technique is based on the notion of approximation: A logical consequence relation is computed by means of sound and progressively “more complete” relations, as well as complete and progressively “more sound” ones. Both sequences generated in this way converge to the original consequence relation and are easier to compute. Moreover they are given a clear semantics based on multivalued logic. With this technique unsoundness and incompleteness are introduced in a controlled way and precisely characterized.
REASONING ABOUT THEORY ADEQUACY. A NEW SOLUTION TO THE QUALIFICATION PROBLEM
Authors: Bouquet Paolo , Giunchiglia Fausto
Published: December 2019

One of the main problems in commonsense reasoning is the qualification problem, ie. the fact that the number of qualifications for most general commonsense statements is virtually infinite. In this paper we argue that a solution to this problem should be based on a (meta) conjecture that the theory used to reason about the world contains all the necessary information. We also show that this theory adequacy conjecture can be made before the application of any of the formalisms proposed in the past, eg. circumscription. Finally, we present a formalization of the solution proposed using contexts and circumscription and use it to solve McCarthy's Glasgow-London-Moscow example.
METAMATHEMATICS OF CONTEXTS
Authors: Buvač Saša , Buvač Vanja , Mason Ian A.
Published: December 2019

In this paper we investigate the simple logical properties of contexts. We describe both the syntax and semantics of a general propositional language of context, and we give a Hilbert style proof system for this language. A propositional logic of context extends classical propositional logic in two ways. Firstly, a new modality, ist(κ,φ), is introduced. It is used to express that the sentence,φ, holds in the context, κ. Secondly, each context has its own vocabulary, i.e. a set of propositional atoms which are defined or meaningful in that context. The main results of this paper are the soundness and completeness of this Hilbert style proof system. We also provide soundness and completeness results (i.e., correspondence theory) for various extensions of the general system. Finally, we prove that our logic is decidable, and give a brief comparison of our semantics to Kripke semantics.
MANAGING MULTIPLE KNOWLEDGE SOURCES IN CONSTRAINT-BASED PARSING OF SPOKEN LANGUAGE
Authors: Harper Mary P. , Helzerman Randall A.
Published: December 2019

In this paper, we describe a system which is capable of utilizing a variety of knowledge sources to select the most appropriate parse for a spoken sentence. These knowledge sources include syntax, semantics, and contextual information. We discuss one way to utilize contextual information when determining the parse for a sentence. At its simplest level, the system can be thought of as a general-purpose query answering system for multiple topical databases. The user's input would be processed by the language processor which interfaces to the databases with the goal of interacting with the correct database in order to provide a reasonable answer to the user's spoken request. Initially, it analyzes a word graph of sentence hypotheses provided by a speech recognizer using general syntactic and semantic rules. Then, if the utterance is still ambiguous, it utilizes context-specific constraints to further refine the analysis. This brings us closer to developing a more general purpose interface for multiple databases.
PARAMETERS AND PARAMETRIZATION IN SPECIFICATION, USING DISTRIBUTIVE CATEGORIES
Authors: Jacobs Bart
Published: December 2019

A specification, as we shall use it here, consists of a signature together with a collection of (non-conditional) equations; these equations involve terms in the ‘distributive type theory’ which is built on top of the signature. This type theory has finite product (x, 1) and coproduct (+, 0) types. Particular simple examples of such specifications are Hagino specifications, which are used to describe inductively defined types. Models of specifications are described in arbitrary distributive categories. In a more categorical approach, one describes models as structure preserving functors. It enables us to define in general what are (a) models of parametrized spefications (in terms of Kan extensions) and (b) models with parameters (in terms of so-called ‘simple slice’ categories). It is shown that in the special case of Hagino specifications, these general definitions specialize to ones in terms of algebras or coalgebras for associated ‘strong’ polynomial functors. Models with parameters of Hagino specifications were described earlier by Cockett and Spencer.
RATIONAL PROCESSES AND LINEAR SYSTEMS IN GSP
Authors: Gabarró J. , Serna M.J.
Published: December 2019

We introduce a new way of describing a subclass of CSP processes in the failures-divergence model. These processes will be called rational, by analogy with rational languages in formal language theory. Usually, rational languages are characterized as a solution of a linear system of equations. In this work we use a restricted set of CSP operators and recursion to define CSP-linear systems. We show that these systems are in many respects similar to linear systems in formal language theory. Our main result states that for linear systems the least fix point solution in a CPO can be obtained using Arden's lemma. Furthermore we give an alternative definition of the class of rational processes in terms of automata. Finally we analyze how the previous result can be extended to other semantic models.
PERFORMANCE EVALUATION OF SYSTEMS DEFINED IN SPECIFICATION LANGUAGE ESTELLE
Authors: Magott Jan
Published: December 2019

In the field of distributed computer systems, in order to specify, verify, and implement systems formally, Formal Description Techniques have been developed. Specification language Estelle, which is an ISO standard, is one of these techniques. Purpose of the present paper is to create a method of performance evaluation for the language Estelle that is based on Petri net methodology. The paper is oriented towards partially automatic generation of performance model for a distributed system - having Estelle specification of this system. A method for finding the performance characteristics of system defined in Estelle is given too.
ON THE SATISFIABILITY PROBLEM FOR LAMPORT'S PROPOSITIONAL TEMPORAL LOGIC OF ACTIONS AND SOME OF ITS EXTENSIONS
Authors: Ramakrishna Y.S.
Published: December 2019

The Temporal Logic of Actions (TLA) devised by Lamport is a logic for proving the correctness of concurrent systems. A distinctive feature of the logic is the use of “action formulae” to encode the “before-after” behaviour of transitions, a feature that is especially suitable for Lamport's transition-axiom method. Abadi has given a complete axiomatization for the propositional fragment of this logic, and conjectured that its validity problem may be in PSPACE. In this paper we confirm that conjecture. In fact we show that the validity problem for TLA is PSPACE-complete. For this we give a space-optimal automata-theoretic decision procedure for TLA. Our result is obtained with respect to a logic which is a conservative extension of Lamport's TLA. Thus our decision procedure applies to the more restricted logic. We show how the automata-theoretic framework handles abstraction, as used in TLA, a feature considered useful for hierarchical and compositional reasoning.
ON A NOTION OF CONCURRENCE
Authors: Korczyńsky Waldemar
Published: December 2019

In the paper Gaussian monoids with zero as a basis for modeling of concurrence and a kind of consistence are proposed and a notion of concurrent system is defined. The main idea is to replace the binary relation of concurrence defined on a set of activities (transitions in Petri nets, events etc.) by a more general notion of independence of multisets.
ON SETS OF TERMS: A STUDY OF A GENERALISATION RELATION AND OF ITS ALGORITHMIC PROPERTIES
Authors: De La Higuera Colin , Daniel-Vatonne Marie-Catherine
Published: December 2019

Signatures, as introduced to cope with semantics of programming languages, provide an interesting framework for knowledge representation. They allow structured and recursive properties that attribute representation does not permit, and at the same time seem to be algorithmically treatable. We recall how a generalisation relation on terms can be introduced by means of the classical special symbol Ω, whose meaning is “indeterminate”, and the partial order inductively defined on the terms. This formalism can nevertheless not take into account negation or disjunction. We provide in this paper a generalisation relation on sets of terms to withdraw these restrictions. This relation has different definitions (syntactical, set-theoretic, and based on a closed world assumption) that are proved to be equivalent for specific classes of signatures. They yield an equivalence relation whose canonical form is studied. We also study the combinatorial and algorithmic issues of the generalisation relation: the following problems are proved to be decidable (on finite data) but generally at least NP-complete: Does set A generalise set B? Are sets A and B equivalent? Is set B the canonical form of set A? Compute the negation of set A.... In the case where one of the sets contains only terms maximal for the generalisation relation, the first three problems are shown to be polynomial.
AXIOMATIZATIONS OF TEMPORAL LOGICS ON TRACE SYSTEMS
Authors: Penczek Wojciech
Published: December 2019

Partial order temporal logics interpreted on trace systems have been shown not to have finitary complete axiomatizations due to the fact that the complexity of their decidability problem is in II11. This paper gives infinitary complete proof systems for several temporal logics on trace systems e.g. Computation Tree Logic with past operators and an essential subset of Interleaving Set Temporal Logic.
TOWARDS AN ALGEBRAIC THEORY OF CONTEXT-FREE LANGUAGES
Authors: Berstel J. , Boasson L.
Published: December 2019

The purpose of the paper is to present the implications of a new definition of context-free languages. The main interests of this approach are first to allow full formal proofs and second to enlight the crucial role of rational closures. The proposed formalism is based on a theorem of Wechler. It is very near to the “radical algebras” of Conway.
SYNCHRONIZATION IN PETRI NETS
Authors: Menezes P. Blauth , Costa J. Félix
Published: December 2019

In “Petti nets are Monoids” by Meseguer and Montanari, categories for Petri nets with and without markings are introduced, where the categorical product and coproduct express the joint behavior of nets. However, this framework lacks structure in the sense that there is no categorical technique to define a composition of nets satisfying some given synchronization specification. In this paper, a synchronization operation is proposed which is a functor induced by some given synchronization prescription at the transition level. Moreover, since this operation is also able to represent the asynchronous composition, the fact that some categories of Petri nets lack coproducts (asynchronous composition) is not anymore a restriction for interaction semantics.
ON NATURAL DEDUCTION IN FIRST-ORDER FIXPOINT LOGICS
Authors: Szalas Andrzej
Published: December 2019

In the current paper we present a powerful technique of obtaining natural deduction proof systems for first-order fixpoint logics. The term fixpoint logics refers collectively to a class of logics consisting of modal logics with modalities definable at meta-level by fixpoint equations on formulas. The class was found very interesting as it contains most logics of programs with e.g. dynamic logic, temporal logic and the μ-calculus among them. In this paper we present a technique that allows us to derive automatically natural deduction systems for modal logics from fixpoint equations defining the modalities.
AN ALGEBRAIC FORMALIZATION OF THE RELATIONSHIP BETWEEN EVIDENTIAL STRUCTURES AND DATA TABLES
Authors: Liau Churn-Jung
Published: December 2019

In this paper, we would like to investigate the relationship between evidential structures (ES)—the basic qualitative structures of Dempster-Shafer theory, and the data table based knowledge representation systems(KRS) subject to rough set analysis. It is shown that an ES has a natural representation as a data table and from a given data table and two of its attributes, an ES can be extracted. We also show that some important operations on ES's can be realized in relational algebra. The results are then generalized to the fuzzy case. Consequently, we further clarify the connection between evidence theory and rough set theory.
SYNTACTIC AND SEMANTIC DEPENDENCE OF ARRAY-ARITHMETIC SENTENCES, WITH AN APPLICATION TO PROGRAM VERIFICATION
Authors: Marcus Leo
Published: December 2019

We present an algorithm that takes a first-order sentence φ in full arithmetic with arrays (with quantification over numbers, and with numerical terms serving as array indices), and builds a test formula that can be used to determine which indices of φ's constituent arrays “really” occur. We call this concept syntactic dependence. We show how to use syntactic dependence as a test for semantic dependence, i.e., the true dependence of φ on the value of an array element. This is useful in truth-maintenance systems or symbolic execution systems, where a sentence may be true in one state but false in the next. More specifically, if we are given an initial state, a sentence (such as φ above) that is true in the initial state, and a list of array elements that may be changing value during a state transition, the algorithm can be used to determine whether φ must remain true after the state transition.
ON FOUR PARTIAL ORDERING SEMANTICS FOR A PROCESS CALCULUS
Authors: Corradini Flavio , Nicola Rocco De
Published: December 2019

Three of the rewriting systems used by Degano, De Nicola and Montanari to provide Milner's CCS with a causality based semantics are compared by using also a fourth intermediate one. These rewriting systems have been used to associate Petri nets, Labelled Event Structures and structured sets of partial orderings to CCS terms. It is proved that the four rewriting systems yield computations from which the same causality relations among the executed actions can be extracted, thus it is established that the four partial ordering transitional semantics do coincide.
SEMANTICS OF TIMED CONCURRENT SYSTEMS
Authors: Dembiński Piotr
Published: December 2019

A truly concurrent and timeless semantics is proposed for a composition of sequential, non-deterministic processes with asynchronous communication. It is shown when this semantics differs from simple interleaving. Implementation-dependent time constraints determine a subset of all computations of the timeless semantics. This set is precisely characterized for given constraints. It is shown how the same set may be generated by a timed transition system, i.e., how to simulate time-constrained and concurrent computations by sequential, non-deterministic system. The paper includes a proof of the correctness of such simulation.
DISCRETE TIME PROCESS ALGEBRA: ABSOLUTE TIME, RELATIVE TIME AND PARAMETRIC TIME
Authors: Baeten J.C.M. , Bergstra J.A.
Published: December 2019

We discuss the key notions of discrete time process algebra in the setting of ACP. Time is measured in discrete slices. The emphasis is on absolute, relative and parametric time notation. Note: Partial support received from ESPRIT Basic Research Action 7166, C0NCUR2.
SYNTAX AND SEMANTICS OF REAL-TIME AND PERFORMANCE EVALUATION EXTENSIONS OF SPECIFICATION LANGUAGE LOTOS
Authors: Huzar Zbigniew , Magott Jan
Published: December 2019

The paper contains extensions of specification language LOTOS in three directions: time-consuming actions, real-time and performance evaluation constructions. Time-consuming actions seem to be more natural than instantaneous actions and they are well suited for real-time system specification and for its performance evaluation. The notions of beginning and termination of the time-consuming action enable to impose time restrictions on beginning and termination times of activities. From performance evaluation point of view it is often important to know explicit how long a specific action has been executed (not when the action has been completed only). We have also introduced a time-out as a specific action. An expressive power of this action has been discussed. We have defined such a performance evaluation extension of LOTOS that can be used as a modelling language for performance evaluation of distributed systems. A true concurrency semantics (in the sense that it refers to the fact that actions with durations may overlap in time) for this extension is defined.
ALGEBRAIC ASPECTS OF ATTRIBUTE DEPENDENCIES IN INFORMATION SYSTEMS
Authors: Düntsch Ivo , Gediga Günther
Published: December 2019

We exhibit some new connections between structure of an information system and its corresponding semilattice of equivalence relations. In particular, we investigate dependency properties and introduce a partial ordering of information systems over a fixed object set U which reflects the sub-semilattice relation on the set of all equivalence relations on U.
HOW TO INTERPRET AND ESTABLISH CONSISTENCY RESULTS FOR SEMANTICS OF CONCURRENT PROGRAMMING LANGUAGES
Authors: Baier Christel , Majster-Cederbaum Mila
Published: December 2019

It is meaningful that a language is provided with several semantic descriptions: e.g. one which serves the needs of the implementor, another one that is suitable for specification and yet another one that will be used to explain the language to the user. In this case one has to guarantee that the various semantics are ‘consistent’. The attempt of this paper is to clarify the notion ‘consistency’ and to present a general framework and theorems for consistency results.
SEMANTICS OF NONSEQUENTIAL TREE-BASED COMPUTATION SCHEMES
Authors: Ehrenfeucht A. , Rozenberg G. , Salomaa K.
Published: December 2019

We consider structured processes that compute changes of valuation functions defined for functional structures, where both the domain and range of each function are the set of sequences over a carrier set. By introducing consistency conditions and certain restrictions on the underlying graph, we obtain a determinism result guaranteeing that for each valuation the structured process computes a unique change of context, i.e., the process defines a partial function on the set of valuations. Employing the determinism theorem we obtain a decomposition result for interpreted trees using a structured process where the edges represent computations in the subtrees.
ATOMICITY AND CONCURRENCY CONTROL IN PROCESS CALCULI
Authors: Ferrari Gian-Luigi
Published: December 2019

A process calculus where atomic actions cooperate via explicit synchronization policies is presented. Bisimulation semantics for the calculus is provided with a sound and complete axiomatization. The problem of modeling concurrency control strategies is also addressed. This paper intends to show that process-algebraic semantics, notably non interleaving semantics, can be used to reason about complex concurrent behaviours.
Tree Automata and Automated Model Building
Authors: Peltier Nicolas
Published: December 2019

The use of regular tree grammars to represent and build models of formulae of first-order logic without equality is investigated. The combination of regular tree grammars with equational constraints provides a powerful and general way of representing Herbrand models. We show that the evaluation problem (i.e. the problem of finding the truth value of a formula in a given model) is decidable when models are represented in the way we propose. We also define a method to build such representations of models for first-order formulae. These results are a powerful extension of our former method for simultaneous search for refutations and models.
Unimprovable Upper Bounds on Time Complexity of Decision Trees
Authors: Moshkov Mikhail
Published: December 2019

The paper is devoted to investigation of behavior of global Shannon functions which produce unimprovable upper bounds on time complexity of decision trees over arbitrary information systems.
Controlled H Systems of Small Radius
Authors: Păun Andrei
Published: December 2019

Several characterizations of recursively enumerable languages are given, using H systems with permitting contexts having splicing rules of small radius. Representations of context-free languages are also obtained in certain particular cases. These results improve previous related results which were recently published. Some open problems are also pointed out.
Rough Sets and 3-valued Lukasiewicz Logic
Authors: Banerjee Mohua
Published: December 2019

A propositional logic for rough sets was proposed in [2]. The present work establishes a relationship between the finitary fragment of this logic and 3-valued Lukasiewicz logic ℒ3. It is also observed that there is an embedding from ℒ3 into the modal system S5.
The ζ-Semantics: A Comprehensive Semantics for Functional Programs
Authors: Chitil Olaf
Published: December 2019

A comprehensive semantics for functional programs is presented, which generalizes the well-known call-by-value and call-by-name semantics. By permitting a separate choice between call-by value and call-by-name for every argument position of every function and parameterizing the semantics by this choice we abstract from the parameter-passing mechanism. Thus common and distinguishing features of all instances of the ζ-semantics, especially call-by-value and call-by-name semantics, are highlighted. Furthermore, a property can be validated for all instances of the ζ-semantics by a single proof. This is employed for proving the equivalence of the given denotational (fixed-point based) and two operational (reduction based) definitions of the ζ-semantics. We present and apply means for very simple proofs of equivalence with the denotational ζ-semantics for a large class of reduction-based ζ-semantics. Our basis are simple first-order constructor-based functional programs with patterns.
Processes in Cause-Effect Systems
Authors: Maggiolo-Schettini Andrea , Matteucci Gionata
Published: December 2019

Cause-Effect (C-E) structures have been proposed as a formalism to describe concurrent and distributed systems. On C-E structures two operations, multiplication and addition, are defined, which allow easy combination and modular development of descriptions. In this paper a concept of process of a C-E structure with an initial state (C-E system) is defined similarly to that of a process of a Condition/Event net in Petri net theory, and operations on processes are studied which correspond to operations on C-E systems.
Unification: Nothing but the Solution of a System of Linear Equations
Authors: Bujosa Andrés , Criado Regino , Hernandez-Medina Miguel A.
Published: December 2019

We use the ring of p-tangles to submerge symbolic expressions in a module structure. Using this structure, the problem of unifying expressions is shown to be equivalent to certain linear systems of equations with coefficients in the ring, whose solution gives the result of unification, if this exists.
An Axiomatization for Regular Processes in Timed Branching Bisimulation
Authors: Fokkink Wan
Published: December 2019

Klusener introduced a timed variant of branching bisimulation. In this paper it is shown that Klusener's axioms for finite process terms, together with two standard axioms for recursion, make a complete axiomatization for regular processes modulo timed branching bisimulation.
On Scott Consequence Systems
Authors: Dimov Georgi , Vakarelov Dimiter
Published: December 2019

The notion of Scott consequence system (briefly, S-system) was introduced by D. Vakarelov in [32] in an analogy to a similar notion given by D. Scott in [26]. In part one of the paper we study the category SSyst of all S-systems and all their morphisms. We show that the category DLat of all distributive lattices and all lattice homomorphisms is isomorphic to a reflective full subcategory of the category SSyst. Extending the representation theory of D. Vakarelov [32] for S-systems in P-systems, we develop an isomorphism theory for S-systems and for Tarski consequence systems. In part two of the paper we prove that the separation theorem for S-systems is equivalent in ZF to some other separation principles, including the separation theorem for filters and ideals in Boolean algebras and separation theorem for convex sets in convexity spaces.
Synchronization of a Line of Identical Processors at a Given Time
Authors: La Torre Salvatore , Napoli Margherita , Parente Domenico
Published: December 2019

We are given a line of n identical processors (finite automata) that work synchronously. Each processor can transmit just one bit of information to the adjacent processors (if any) to the left and to the right. The computation starts at time 1 with the leftmost processor in an initial state and all other processors in a quiescent state. Given the time f(n), the problem is to set (synchronize) all the processors in a particular state for the first time, at the very same instant f(n). This problem is also known as the Firing Squad Synchronization Problem and was introduced by Moore in 1964. Mazoyer has given a minimal time solution with the least number of different states (six) and very recently he has given a minimal time solution for the constrained problem in which adjacent processors can exchange only one bit. In this paper we present solutions that synchronize the line at a given time, expressed as a function of n. In particular we give solutions that synchronize at the times nlogn, n√n, n2 and 2n. Moreover we also show how to compose solutions in such a way to obtain synchronizing solutions for all times expressed by polynomials with nonnegative coefficients. Clearly all such solutions work also in the general case when the bit constraint is relaxed.
On the Semantics of a Semantic Network
Authors: Analyti Anastasia , Spyratos Nicolas , Constantopoulos Panos
Published: December 2019

We elaborate on the semantics of an enhanced object-oriented semantic network, where multiple instantiation, multiple specialization, and meta-classes are supported for both kinds of objects: entities and properties. By semantics of a semantic network, we mean the information (both explicit and derived) that the semantic network carries. Several data models use semantic networks to organize information. However, many of these models do not have a formalism defining what the semantics of the semantic network is. In our data model, in addition to the Isa relation, we consider a stronger form of specialization for properties, that we call restriction isa, or Risa for short. The Risa relation expresses property value refinement. A distinctive feature of our data model is that it supports the interaction between Isa and Risa relations. The combination of Isa and Risa provides a powerful conceptual modeling mechanism. The user declares objects and relations between objects through a program. Reasoning is done through a number of (built-in) inference rules that allow for derivations both at instance and schema level. Through the inference rules, new objects and new relations between objects are derived. In our data model, inherited properties are considered to be derived objects. In addition to the inference rules, a number of (built-in) system constraints exist for checking the validity of a program.
Characterization of the Expressive Power of Silent Transitions in Timed Automata
Authors: Bérard Béatrice , Petit Antoine , Diekert Volker , Gastin Paul
Published: December 2019

Timed automata are among the most widely studied models for real-time systems. Silent transitions, i.e., ϵ-transitions, have already been proposed in the original paper on timed automata by Alur and Dill [3]. We show that the class TLϵ of timed languages recognized by automata with ϵ-transitions, is more robust and more expressive than the corresponding class TL without ϵ-transitions. We then focus on ϵ-transitions without reset, i.e. ϵ-transitions which do not reset clocks. We propose an algorithm to construct, given a timed automaton, an equivalent one without such transitions. This algorithm is in two steps, it first suppresses the cycles of ϵ-transitions without reset and then the remaining ones. Then, we prove that a timed automaton such that no ϵ-transition which resets clocks lies on any directed cycle, can be effectively transformed into a timed automaton without ϵtransitions. Interestingly, this main result holds under the assumption of non-Zenoness and it is false otherwise. To complete the picture, we exhibit a simple timed automaton with an ϵ-transition, which resets some clock, on a cycle and which is not equivalent to any ϵ-free timed automaton. To show this, we develop a promising new technique based on the notion of precise action. This paper presents a synthesis of the two conference communications [9] and [13].
On the Average-Case Complexity of the Graph Reliability Problem on Gaussian Distributions
Authors: Burago Dmitri , de Rougemont Michel
Published: December 2019

We introduce classes of narrow graphs (including grid strips of fixed width), for which the graph reliability problem admits a polynomial time algorithm. Using this algorithm, we show that graph reliability is computable in polynomial time for the average complexity with respect to a Gaussian distribution. The latter is defined as follows: the vertices are numbered by integers {1,2, ...n}, and the probability that an edge between i and j is present is e−|i−j|2.
The Modified Oja-RLS Algorithm, Stochastic Convergence Analysis and Application for Image Compression
Authors: Skarbek Władysław , Pietrowcew Adam , Sikora Radosław
Published: December 2019

The results of theoretical analysis for stochastic convergence of the modified Oja-RLS learning rule are presented. The rule is used to find Karhunen Loeve Transform. Based on this algorithm, an image compression scheme is developed by combining approximated 2D KLT transform and JPEG standard quantization and entropy coding stages. Though 2D KLT transform is of higher complexity than 2D DCT, the resulting PSNR quality of reconstructed images is better even by 2[dB].
Fixed Point Equations Inside the Algebra of Normal Forms
Authors: Böhm Corrado
Published: December 2019

Solutions of the equations X = ZX and X = XZ are found and discussed for Z, X normal terms of the lambda-calculus. Obviously fixed point combinators are of no help. Solutions will be independent from any kind of gödelization or coding of data structures, they will be provided by typeless self-application. Different approaches will be shown: algebraic properties, one side invertibility and idempotency. Certain subsets of proper combinators and Church algebras between them will be proved to be domains consisting only of fixed points of combinators.
On Accepting Pure Lindenmayer Systems
Authors: Bordihn Henning , Fernau Henning , Holzer Markus
Published: December 2019

We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.
The Membership Problem for Switching Classes with Skew Gains
Authors: Hage Jurriaan
Published: December 2019

Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching classes are equivalence classes of gain graphs under the switching operation. The membership (or equivalence) problem is important to the theory of switching classes. The problem is to decide for two given skew gain graphs, on the same underlying graph and having gains from the same group, whether or not they belong to the same switching class. We give efficient algorithms. If a certain skew gain graph in the switching class has only abelian gains, then we can reduce the membership problem to an elegant problem on anti-involutions. Finally we show that the word problem can be reduced to the general membership problem, thereby establishing undecidability of the latter for some groups.
Tableaux Based Decision Procedures for Modal Logics of Confluence and Density
Authors: del Cerro Luis Fariñas , Gasquet Olivier
Published: December 2019

In this paper we present a decision procedures for modal logics with transitive models together with additionnal properties like confluence and density. These procedures are tableaux-based, and we show how to handle them in this well-known framework by generalizing usual tableaux (which are trees) to richer structures: directed acyclic graphs.
On Topological Hierarchies of Temporal Properties
Authors: Baier Christel , Kwiatkowska Marta
Published: December 2019

The classification of properties of concurrent programs into safety and liveness was first proposed by Lamport [22]. Since then several characterizations of hierarchies of properties have been given, see e.g. [3, 20, 9, 21]; this includes syntactic characterizations (in terms classes of formulas of logics such as the linear temporal logic) as well as extensional (as sets of computations in some abstract domain). The latter often admits a topological characterization with respect to the natural topologies of the domain of computations. We introduce a general notion of a linear time model of computation which consists of partial and completed computations satisfying certain axioms. The model is endowed with a natural topology. We show that the usual topologies on strings, Mazurkiewicz traces and pomsets arise as special cases. We then introduce a hierarchy of properties including safety, liveness, guarantee, response and persistence properties, and show that our definition subsumes the hierarchies of: Alpern & Schneider [3]; Chang, Manna & Pnueli [9]; and Kwiatkowska, Peled & Penczek [21]. Syntactic characterizations of the properties in the hierarchy in terms of temporal logic are also studied.
Deterministic and Nondeterministic Decision Trees for Rough Computing
Authors: Moshkov Mikhail
Published: December 2019

In the paper, infinite information systems are considered which are used in pattern recognition, discrete optimization, computational geometry. Depth and size of deterministic and nondeterministic decision trees over such information systems are studied. Two classes of infinite information systems are investigated. Systems from these classes are best from the point of view of time complexity and space complexity of deterministic as well as nondeterministic decision trees. In proofs methods of test theory [1] and rough set theory [6, 9] are used.