1.

The atnext/atprevious Hierarchy on the Starfree Languages
- Bernd Borchert; Pascal Tesson
The temporal logic operators atnext and atprevious are alternatives for the operators until and since. P atnext Q has the meaning: at the next position in the future where Q holds it holds P. We define an asymmetric but natural notion of depth for the expressions of this linear temporal logic. The sequence of classes atn of languages expressible via such depth-n expressions gives a parametrization of the starfree regular languages which we call the atnext/atprevious ierarchy, or simply the at hierarchy. It turns out that the at hierarchy equals the hierarchy given by the n-fold weakly iterated block product...

2.

Structure Theorem and Strict Alternation Hierarchy for FO² on Words
- Philipp Weis; Neil Immerman
It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and well-studied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to FO^2[<] and FO²[<, Suc], the latter of which includes the binary successor relation in addition to the linear ordering on string positions. For both languages, our structure theorems show exactly what is expressible using a given quantifier depth, n, and using m blocks of alternating quantifiers,...

3.

Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
- Manfred Kufleitner; Alexander Lauser
We consider the quantifier alternation hierarchy within two-variable first-order logic FO²[<, suc] over finite words with linear order and binary successor predicate. We give a single identity of omega-terms for each level of this hierarchy. This shows that for a given regular language and a non-negative integer m it is decidable whether the language is definable by a formula in FO²[<, suc] which has at most m quantifier alternations. We also consider the alternation hierarchy of unary temporal logic TL[X, F, Y, P] defined by the maximal number of nested negations. This hierarchy coincides with the FO²[<, suc] quantifier alternation...

4.

Two-variable first order logic with modular predicates over words
- Luc Dartois; Charles Paperman
We consider first order formulae over the signature consisting of the symbols of the alphabet, the symbol < (interpreted as a linear order) and the set MOD of modular numerical predicates. We study the expressive power of FO 2 [<, MOD], the two-variable first order logic over this signature, interpreted over finite words. We give an algebraic characterization of the corresponding regular languages in terms of their syntactic morphisms and we also give simple unambiguous regular expressions for them. It follows that one can decide whether a given regular language is captured by FO 2 [<, MOD]. Our proofs rely...

5.

Logic meets algebra: the case of regular languages
- Pascal Tesson; Denis Thérien
The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Büchi, regular languages have been classified according to their descriptive complexity, i.e. the type of logical formalism required to define them. The algebraic point of view on automata is an essential complement of this classification: by providing alternative, algebraic characterizations for the classes, it often yields the only opportunity for the design of algorithms that decide expressibility in some logical fragment. We survey the existing results relating the expressibility of regular languages in logical fragments of MSO[S] with algebraic...

6.

Structure Theorem and Strict Alternation Hierarchy for FO² on Words
- Philipp Weis; Neil Immerman
It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and well-studied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to both the case with and without a successor relation. For both languages, our structure theorems show exactly what is expressible using a given quantifier depth, n, and using m blocks of alternating quantifiers, for any m ≤ n. Using these characterizations, we prove, among other results,...

7.

Tree languages defined in first-order logic with one quantifier alternation
- M. Bojańczyk; L. Segoufin
8.

Dynamics of non-archimedean Polish groups
- Alexander S. Kechris
A topological group G is Polish if its topology admits a compatible separable complete metric. Such a group is non-archimedean if it has a basis at the identity that consists of open subgroups. This class of Polish groups includes the profinite groups and (Qp, +) but our main interest here will be on non-locally compact groups. In recent years there has been considerable activity in the study of the dynamics of Polish non-archimedean groups and this has led to interesting interactions between logic, finite combinatorics, group theory, topological dynamics, ergodic theory and representation theory. In this paper I will give...

9.

TWO-WAY UNARY TEMPORAL LOGIC OVER TREES
- Mikołaj Bojańczyk
We consider a temporal logic EF + F −1 for unranked, unordered finite trees. The logic has two operators: EFϕ, which says “in some proper descendant ϕ holds”, and F −1 ϕ, which says “in some proper ancestor ϕ holds”. We present an algorithm for deciding if a regular language of unranked finite trees can be expressed in EF+F −1. The algorithm uses a characterization expressed in terms of forest algebras.

10.

Uniform circuits, & Boolean proof nets
- Virgile Mogbil; Vincent Rahli
The relationship between Boolean proof nets of multiplicative linear logic (APN) and Boolean circuits has been studied [Ter04] in a non-uniform setting. We refine this results by taking care of uniformity: the relationship can be expressed in term of the (Turing) polynomial hierarchy. We give a proofs-as-programs correspondence between proof nets and deterministic as well as non-deterministic Boolean circuits with a uniform depth-preserving simulation of each other. The Boolean proof nets class m&BN(poly) is built on multiplicative and additive linear logic with a polynomial amount of additive connectives as the nondeterministic circuit class NNC(poly) is with non-deterministic variables. We obtain...

11.

Uniform circuits, & Boolean proof nets
- Virgile Mogbil; Vincent Rahli
The relationship between Boolean proof nets of multiplicative linear logic (APN) and Boolean circuits has been studied [Ter04] in a non-uniform setting. We refine the results taking care of uniformity: the relationship can be expressed in term of the (Turing) polynomial hierarchy. We give a proofs-as-programs correspondence between proof nets and deterministic as well as non-deterministic Boolean circuits with a uniform depth-preserving simulation of each other. The Boolean proof nets class m&BN(poly) is built on multiplicative and additive linear logic with a polynomial amount of additive connectives as the nondeterministic circuit class NNC(poly) is with non-deterministic variables. We obtain uniform-APN...

12.

La no consolidación político-económica del MERCOSUR
- Döring, Matías Nicolás
Las problemáticas que afectan al mundo han superado y limitado el ámbito de incumbencia de la soberanía de los Estados. Ante ello conforman uniones, integraciones o acuerdos políticos, militares, económicos y/o sociales para fortalecerla y generar “densidad política”.
Paradójicamente, esta interdependencia compleja es una nueva limitación a la soberanía por los compromisos asumidos. Los Estados entonces utilizan principios de relaciones políticas y jurídicas internacionales para contrarrestar otros según convenga. Así, para Krasner (2001) se impone una lógica de circunstancias (conducta que los gobernantes creen más conveniente para maximizar sus preferencias) por sobre una lógica de pertinencia (conducta adecuada según principios, roles...

13.

Stéphane Beel architects. Ghent
- Campo Baeza, Alberto
I have always been impressed by the clear and precise work of STEPHANE BEEL ARCHITECTS, which is tremendous in quality , if not abundant in quantity. Beel creates what I would call silent architecture - silent ln the way of a Mies buildlng, all clarity and logic.

14.

Customer dominant value creation: a theoretical response to a recent call for a consumer dominant logic for marketing
- Moutinho, Luiz; Anker, Thomas; Sparks, Leigh; Gronroos, Christian
No abstract available.

15.

Formal Analysis of Fairness for Optimistic Multiparty Contract Signing Protocol
- Li, Xiaoru; Li, Xiaohong; Xu, Guangquan; Hu, Jing; Feng, Zhiyong
Optimistic multiparty contract signing (OMPCS) protocols are proposed for exchanging multiparty digital signatures in a contract. Compared with general two-party exchanging protocols, such protocols are more complicated, because the number of protocol messages and states increases considerably when signatories increase. Moreover, fairness property in such protocols requires protection from each signatory rather than from an external hostile agent. It thus presents a challenge for formal verification. In our analysis, we employ and combine the strength of extended modeling language CSP# and linear temporal logic (LTL) to verify the fairness of OMPCS protocols. Furthermore, for solving or mitigating the state space...

16.

Formalization of Function Matrix Theory in HOL
- Shi, Zhiping; Liu, Zhenke; Guan, Yong; Ye, Shiwei; Zhang, Jie; Wei, Hongxing
Function matrices, in which elements are functions rather than numbers, are widely used in model analysis of dynamic systems such as control systems and robotics. In safety-critical applications, the dynamic systems are required to be analyzed formally and accurately to ensure their correctness and safeness. Higher-order logic (HOL) theorem proving is a promise technique to match the requirement. This paper proposes a higher-order logic formalization of the function vector and the function matrix theories using the HOL theorem prover, including data types, operations, and their properties, and further presents formalization of the differential and integral of function vectors and function...

17.

Usability Analysis of Collision Avoidance System in Vehicle-to-Vehicle Communication Environment
- Cho, Hong; Kim, Gyoung-Eun; Kim, Byeong-Woo
Conventional intelligent vehicles have performance limitations owing to the short road and obstacle detection range of the installed sensors. In this study, to overcome this limitation, we tested the usability of a new conceptual autonomous emergency braking (AEB) system that employs vehicle-to-vehicle (V2V) communication technology in the existing AEB system. To this end, a radar sensor and a driving and communication environment constituting the AEB system were simulated; the simulation was then linked by applying vehicle dynamics and control logic. The simulation results show that the collision avoidance relaxation rate of V2V communication-based AEB system was reduced compared with that...

18.

Reconstitution of a Minimal Ribosome-Associated Ubiquitination Pathway with Purified Factors
- Shao, Sichen; Hegde, Ramanujan S.
Ribosomes stalled on aberrant mRNAs engage quality control mechanisms that degrade the partially translated nascent polypeptide. Ubiquitination of the nascent protein is mediated by the E3 ligase Listerin via a mechanism involving ribosome subunit dissociation. Here, we reconstitute ribosome-associated ubiquitination with purified factors to define the minimal components and essential steps in this process. We find that the primary role of the ribosome splitting factors Hbs1, Pelota, and ABCE1 is to permit Listerin access to the nascent chain. Listerin alone can discriminate 60S- from 80S-nascent chain complexes to selectively ubiquitinate the former. Splitting factors can be bypassed by artificially removing...

19.

‘Trust and teamwork matter’: Community health workers' experiences in integrated service delivery in India
- Mishra, Arima
A comprehensive and integrated approach to strengthen primary health care has been the major thrust of the National Rural Health Mission (NRHM) that was launched in 2005 to revamp India's rural public health system. Though the logic of horizontal and integrated health care to strengthen health systems has long been acknowledged at policy level, empirical evidence on how such integration operates is rare. Based on recent (2011–2012) ethnographic fieldwork in Odisha, India, this article discusses community health workers' experiences in integrated service delivery through village-level outreach sessions within the NRHM. It shows that for health workers, the notion of integration...

20.

Tuning the threshold voltage of carbon nanotube transistors by n-type molecular doping for robust and flexible complementary circuits
- Wang, Huiliang; Wei, Peng; Li, Yaoxuan; Han, Jeff; Lee, Hye Ryoung; Naab, Benjamin D.; Liu, Nan; Wang, Chenggong; Adijanto, Eric; Tee, Benjamin C.-K.; Morishita, Satoshi; Li, Qiaochu; Gao, Yongli; Cui, Yi; Bao, Zhenan
Highly noise-resistant logic gates are needed for large-scale circuits. This was challenging previously with carbon nanotube circuits due to the lack of control of the threshold voltages of nanotube transistors. We demonstrate the use of dopants to tune the charge carrier density of carbon nanotubes films and hence precisely control the threshold voltages of carbon nanotube transistors. This doping method is highly versatile and can be applied through inkjet printing. With this technique, we demonstrate highly noise-resistant and low power consumption carbon nanotube logic gates on a flexible substrate. This work places carbon nanotubes in a highly competitive position for...