Search results for "formal"

On bijections vs. unary functions

1996

A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.

Tally languages accepted by alternating multitape finite automata

1997

We consider k-tape 1-way alternating finite automata (k-tape lafa). We say that an alternating automaton accepts a language L\(\subseteq\)(Σ*)k with f(n)-bounded maximal (respectively, minimal) leaf-size if arbitrary (respectively, at least one) accepting tree for any (w1, w2,..., wk) ∈ L has no more than $$f\mathop {(\max }\limits_{1 \leqslant i \leqslant k} \left| {w_i } \right|)$$ leaves. The main results of the paper are the following. If k-tape lafa accepts language L over one-letter alphabet with o(log n)-bounded maximal leaf-size or o(log log n)-bounded minimal leaf-size then the language L is semilinear. Moreover, if a language L is accepted with o(log log(n))-bounded minimal (respe…

Compactness of a conformal boundary of the Euclidean unit ball

2011

We study conformal metrics d‰ on the Euclidean unit ball B n : We assume that either the density ‰ associated with the metric d‰ satisfies a logarithmic volume growth condition for small balls or that ‰ satisfies a Harnack inequality and a suitable sub-Euclidean volume growth condition. We prove that the ‰-boundary @‰ B n is homeomorphic to S ni1 if and only if @‰ B n is compact. In the planar case, the compactness of @‰ B 2 is further equivalent to local connectivity of the ‰-boundary together with the boundedness of (B 2 ;d‰):

Defence strategies in an online community of caregivers

2021

Purpose The purpose of this paper is to understand caregivers’ discursive constructions and responses to their unwanted (family and social) role as resulting in exchanges on social media. Online group platforms are understood as particularly suitable for the expression of intimate feelings among adults, for meeting and exhibiting stigma issues, and for the circulation of information and support (Suler, 2004; McCormack, 2010; Pounds et al., 2018). Design/methodology/approach This paper draws from digital Conversation Analysis (Giles et al., 2015), and considers data after combining quantitative (corpus analysis) and qualitative methods, from a critical discourse analysis perspective. The St…

K4-free Graphs as a Free Algebra

2017

International audience; Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they …

Learning with belief levels

2008

AbstractWe study learning of predicate logics formulas from “elementary facts,” i.e. from the values of the predicates in the given model. Several models of learning are considered, but most of our attention is paid to learning with belief levels. We propose an axiom system which describes what we consider to be a human scientist's natural behavior when trying to explore these elementary facts. It is proved that no such system can be complete. However we believe that our axiom system is “practically” complete. Theorems presented in the paper in some sense confirm our hypothesis.

An example of cancellation of infinities in the star-quantization of fields

1993

Within the *-quantization framework, it is shown how to remove some of the divergences occurring in theλo 2 4 -theory by introducing aλ-dependent *-product cohomologically equivalent to the normal *-product.

Systematic reasoning: Formal or postformal cognition?

1995

The focus of this study was to investigate the relationship between formal and postformal systematic metasystematic reasoning. Shayer's (1978) chemicals task and a modified version of Kuhn and Brannock's (1977) plant task were used to measure formal thinking and Commons, Richard, and Kuhn's (1982) multisystem task and balance-beam task to detect postformal reasoning. Subjects were university students from the humanities and social sciences (N=35). For each subject, a composite score was defined by taking into account the highest score in the tasks measuring the same developmental stage. Findings indicated that composite scores of formal and postformal reasoning were significantly correlated…

Software Architectures for Human-Machine Interaction Using Natural Language

Il linguaggio naturale rappresenta un sistema di comunicazione a carattere inferenziale in opposizione ai sistemi di comunicazione a codice che non prevedono una forma di ragionamento intelligente da parte del ricevente, ma si basano sul riconoscimento di patterns dell'informazione. In un sistema di comunicazione di tipo inferenziale, infatti, si parte dal presupposto che il ricevente abbia una certa "intelligenza" e sia, quindi, capace di comprendere, elaborare ed inferire il contenuto informativo di una comunicazione attraverso ragionamenti su un background di conoscenze (come modelli di mondo e di linguaggio) condivisi sia dalla sorgente che dal destinatario. L'attività di ricerca, svolt…

Descriptive Complexity, Lower Bounds and Linear Time

1999

This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of lo…