Search results for "d AU"
showing 10 items of 747 documents
FO^2 with one transitive relation is decidable
2013
We show that the satisfiability problem for the two-variable first-order logic, FO^2, over transitive structures when only one relation is required to be transitive, is decidable. The result is optimal, as FO^2 over structures with two transitive relations, or with one transitive and one equivalence relation, are known to be undecidable, so in fact, our result completes the classification of FO^2-logics over transitive structures with respect to decidability. We show that the satisfiability problem is in 2-NExpTime. Decidability of the finite satisfiability problem remains open.
Unambiguous recognizable two-dimensional languages
2006
We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of UREC are presented. Finally we show that it is undecidable whether a given tiling system is unambiguous.
Weak and strong recognition by 2-way randomized automata
1997
Languages weakly recognized by a Monte Carlo 2-way finite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way finite automaton with no(n) states. This improves dramatically over the previously known result by M.Karpinski and R.Verbeek [10] which is also nontrivial since these languages can be nonregular [5]. For tally languages the increase in the number of states is proved to be only polynomial, and these languages are regular.
Block-Deterministic Regular Languages
2001
We introduce the notions of blocked, block-marked and blockdeterministic regular expressions. We characterize block-deterministic regular expressions with deterministic Glushkov block automata. The results can be viewed as a generalization of the characterization of one-unambiguous regular expressions with deterministic Glushkov automata. In addition, when a language L has a block-deterministic expression E, we can construct a deterministic finite-state automaton for L that has size linear in the size of E.
Alpha 1 adrenoceptor expression in skin, nerves and blood vessels of patients with painful diabetic neuropathy
2021
Abstract Diabetic neuropathy (dNP) patients often suffer from severe neuropathic pain. It was suggested that alpha-1 adrenoceptor (α1-AR) hyperresponsiveness contributes to pain in dNP. The aim of our study was to quantify α1-AR expression using immunohistochemistry in skin biopsies of nine patients with painful diabetic neuropathy compared to 10 healthy controls. Additionally, the association between α1-AR expression and activation with spontaneous and sympathetically maintained pain (SMP) induced by intradermal injection of the α1-agonist phenylephrine was investigated. For control purposes the α2-agonist clonidine was injected in a different session. We found that dermal nerve density wa…
Epichristoffel Words and Minimization of Moore Automata
2014
This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft's algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft's minimization algorithm. The use of this variant makes simpler the computation of the running time and consequ…
A note on renewal systems
1992
Abstract A renewal system is a symbolic dynamical system generated by free concatenations of a finite set of words. In this paper we prove that, given two systems which are both renewal and Markov systems, it is decidable whether they are topologically conjugate. The proof makes use of the methods and the techniques of formal language theory.
On Sturmian Graphs
2007
AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.
A decidable word problem without equivalent canonical term rewriting system
1989
We present a weak associative single-axiom system having the following property: the word problem is decidable with an efficient algorithm even though there does not exist any finite equivalent canonical term rewriting system.
Forbidden words in symbolic dynamics
2000
AbstractWe introduce an equivalence relation≃between functions from N to N. By describing a symbolic dynamical system in terms of forbidden words, we prove that the≃-equivalence class of the function that counts the minimal forbidden words of a system is a topological invariant of the system. We show that the new invariant is independent from previous ones, but it is not characteristic. In the case of sofic systems, we prove that the≃-equivalence of the corresponding functions is a decidable question. As a more special application, we show, by using the new invariant, that two systems associated to Sturmian words having “different slope” are not conjugate.