Search

Every univariate rational series over an algebraically closed field is shown to be realised by some polynomially ambiguous unary weighted automaton. Unary weighted automata over algebraically closed fields thus always admit polynomially ambiguous equivalents. On the other hand, it is shown that this property does not hold over any other field of characteristic zero, generalising a recent observation about unary weighted automata over the field of rational numbers. [ABSTRACT FROM AUTHOR]

This paper deals with one-way and two-way weighted automata. When the semiring of weights is commutative, we prove that unambiguous one-way automata, unambiguous two-way automata and deterministic two-way automata realize the same (rational) power series. If the semiring of weights is not commutative, unambiguous one-way automata and deterministic two-way automata realize the same rational power series, but unambiguous two-way automata may realize non rational power series. [ABSTRACT FROM AUTHOR]

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2 Θ ( n 2 ) states (B. von Braunmühl and R. Verbeek, 1983 [8] ), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4] ). This paper demonstrates that the same worst-case 2 Θ ( n 2 ) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2 Θ ( n 2 ) , and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2 Θ ( n 2 ) . [ABSTRACT FROM AUTHOR]

Abstract: Okhotin showed an exponential trade-off in the conversion from nondeterministic unary automata to unambiguous nondeterministic unary automata. We show that the trade-off in the case of unary symmetric difference automata to finitely (structurally) ambiguous unary symmetric difference automata is linear with constant 1 in the number of states. In particular, for every n-state unary nondeterministic symmetric difference automaton, there is an equivalent finitely (structurally) ambiguous n-state unary symmetric difference nondeterministic automaton. We also consider the complexity of deciding unambiguity for k-deterministic finite automata and investigate the interplay between ambiguity and structural ambiguity. [Copyright &y& Elsevier]

The class of languages captured by Constrained Automata (CA) that are unambiguous is shown to possess more closure properties than the provably weaker class captured by deterministic CA. Problems decidable for deterministic CA are nonetheless shown to remain decidable for unambiguous CA, and testing for regularity is added to this set of decidable problems. Unambiguous CA are then shown incomparable with deterministic reversal-bounded machines in terms of expressivity, and a deterministic model equivalent to unambiguous CA is identified. [ABSTRACT FROM AUTHOR]

The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for inputs of size n. For every natural number k we construct a family $(L_{r}^{k}\;|\;r\in \mathbb{N})$ of languages which can be recognized by NFA's with size k⋅poly( r) and ambiguity O( n), but $L_{r}^{k}$ has only NFA's with size exponential in r, if ambiguity o( n) is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, SIAM J. Comput. 19:1263-1282, , Leung, SIAM J. Comput. 27:1073-1082, ). [ABSTRACT FROM AUTHOR]

We present a model of automaton for picture language recognition, called Wang automaton, which is based on labeled Wang tiles. Wang automata combine features of both online tessellation acceptors and 4-way automata: as in online tessellation acceptors, computation assigns states to each picture position; as in 4-way automata, the input head visits the picture moving from one pixel to an adjacent one, according to some scanning strategy. Wang automata recognize the class REC, i.e. they are equivalent to tiling systems or online tessellation acceptors, and hence strictly more powerful than 4-way automata. We also introduce a natural notion of determinism for Wang automata, and study the resulting class, extending the more traditional approach of diagonal-based determinism, used e.g. by deterministic tiling systems. In particular, we prove that the concept of row (or column) ambiguity defines the class of languages recognized by Wang automata directed by boustrophedonic scanning strategies. [ABSTRACT FROM AUTHOR]

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties. [ABSTRACT FROM AUTHOR]

Abstract: The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. The family DREC(1) of deterministic languages over a one-letter alphabet is characterized as both (DOTA)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and (2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-letter alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-letter alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations. [Copyright &y& Elsevier]

This paper presents a monitor positioning algorithm to determine the optimal number of power quality monitors and to decide the locations for a given distribution system. From graph theory, the system topology is formulated into a coverage matrix. The weighting factors of each component are newly defined from the guidelines of monitor positioning suggested. Weighting factors represent the degree of importance in the system topology. Ambiguity indices are suggested to evaluate the monitor locations in terms of topological ambiguity. The optimal number and locations are determined from the optimization routine utilizing the weighting factor and the ambiguity indices. The proposed approach can realize the expert's knowledge on monitor positioning into a sophisticated automatic computing algorithm. [ABSTRACT FROM AUTHOR]

Restarting automata can be considered as a machine model as well as regulated rewriting systems. We introduce a measure of ambiguity for restarting automata which recognizes a language as a projection of its characteristic language (containing also auxiliary—non-input—symbols) into its input alphabet. Based on this measure we define an ambiguity measure of languages. This measure can be considered as a measure of non-determinism of languages. We show that there is an infinite hierarchy with respect to the degree of ambiguity even inside linear languages and that there are linear languages with a linear ambiguity. [ABSTRACT FROM AUTHOR]

Abstract: Regular expressions with numeric occurrence indicators are an extension of traditional regular expressions, which let the required minimum and the allowed maximum number of iterations of subexpressions be described with numeric parameters. We consider the problem of testing whether a given regular expression E with numeric occurrence indicators is 1-unambiguous or not. This condition means, informally, that any prefix of any word accepted by expression E determines a unique path of matching symbol positions in E. One-unambiguity appears as a validity constraint in popular document schema languages such as SGML and XML DTDs (document type definitions) and XML Schema; the last one both includes numeric occurrence indicators and requires one-unambiguity of expressions. Previously published solutions for testing the one-unambiguity of regular expressions with numeric occurrence indicators are either erroneous or require exponential time. The main contribution of this paper is a polynomial-time method for solving this problem, and a formal proof of its correctness. [Copyright &y& Elsevier]

Abstract: The theory of two-dimensional languages as a generalization of formal string languages was motivated by problems arising from image processing and pattern recognition, and also concerns models of parallel computing. Here we investigate power series on pictures. These are functions that map pictures to elements of a semiring and provide an extension of two-dimensional languages to a quantitative setting. We assign weights to different devices, ranging from picture automata to tiling systems. We will prove that, for commutative semirings, the behaviours of weighted picture automata are precisely alphabetic projections of series defined in terms of rational operations, and also coincide with the families of series characterized by weighted tiling or weighted domino systems. [Copyright &y& Elsevier]

We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations. [ABSTRACT FROM AUTHOR]

Abstract: Context-free grammars and languages with infinite ambiguity can be distinguished by the growth rate of their ambiguity with respect to the length of the words. So far the least growth rate known for a divergent inherent ambiguity function was logarithmic. Roughly speaking we show that it is possible to stay below any computable function. More precisely let be an arbitrary computable divergent total non-decreasing function. Then there is a context-free language L with a divergent inherent ambiguity function g below , i.e., for each . This result is an immediate consequence of two other results which are of independent interest. The first result says that there is a linear context-free grammar G with so called unambiguous turn position whose ambiguity function is below . The second one states that any ambiguity function of a cycle-free context-free grammar is an inherent ambiguity function of some context-free language. [Copyright &y& Elsevier]

Summary: Health level 7 (HL7) is a standard for medical information exchange. It defines data transfers for the application systems in the healthcare environment. Alternatively, the extensible markup language (XML) is a standard for data exchange using the Internet. If exchange messages follow the content and the sequence defined by HL7 and are expressed in the XML format, the system may benefit from the advantages of both standards. In creating the XML schema, we found ambiguities in HL7 message structures that cause the XML schema to be non-deterministic. These ambiguous expressions are summarized within 12 structures and can be replaced with equivalent or similar unambiguous structures. The finite state automata are used to verify expression equivalence. Applying this schema, an XML document may eliminate redundant segment group definitions and make the structure simple and easy to reproduce. In this paper, we discuss the methods and our experience in resolving ambiguous problems in HL7 messages to generate a deterministic XML schema. [Copyright &y& Elsevier]

Abstract: Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. Furthermore, the proof is constructive. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity. [Copyright &y& Elsevier]

We study the ambiguity, or “many-to-one”-ness, of two-argument, one-way functions that are strong (that is, hard to invert even if one of their arguments is given), total, and associative. Such powerful one-way functions are the basis of a cryptographic paradigm described by Rabi and Sherman (Inform. Process. Lett. 64(2) (1997) 239) and were shown by Hemaspaandra and Rothe (J. Comput. System Sci. 58(3) (1999) 648) to exist exactly if standard one-way functions exist.Rabi and Sherman (1997) show that no total, associative function defined over a universe having at least two elements is one-to-one. We show that if P≠UP, then, for every d∈N+, there is an O(log1/d n)-to-one, strong, total, associative, one-way function σd. We argue that this bound is tight in the sense that any total, associative function having similar properties to σd but not necessarily strong or one-way must have at least the same order of magnitude of ambiguity as σd has. We demonstrate that the techniques used in proving the above-stated results easily apply to other classes of total, associative functions.We provide a complete characterization for the existence of strong, total, associative, one-way functions whose ambiguity approaches the lower bounds we provide. We say a language is in PolylogP if there exists a polynomial-time Turing machine M accepting the language such that for some d∈R+ it holds that M has on each string x at most O(logd n) accepting paths, where n=|x|. We show that P≠PolylogP if and only for some d∈R+ there exists an O(logd n)-to-one, strong, total, associative, one-way function. [Copyright &y& Elsevier]

We extend the well-known notions of ambiguity and of degrees of ambiguity of finitary context free languages to the case of omega context free languages (ω-CFL) accepted by Bu¨chi or Muller pushdown automata. We show that these notions may be defined independently of the Bu¨chi or Muller acceptance condition which is considered. We investigate first properties of the subclasses of omega context free languages we get in that way, giving many examples and studying topological properties of ω-CFL of a given degree of ambiguity. [Copyright &y& Elsevier]

Research suggesting both a superiority of frequencies over single-event probabilities and of smaller reference classes over very large reference classes have utilized tasks that vary in computational complexity. The present research sought to simply and directly evaluate if -- apart from simplifying statistical inference tasks -- frequencies and small reference classes are clearer than other formats. After eliminating possible computational confounds, simple frequencies (based on small reference classes, e.g. 1/3) and to some extent relative frequencies (percentages, e.g. 33%) were perceived as clearer than absolute frequencies (based on very large reference classes, e.g. 90 million Americans) and single-event probabilities (e.g. 0.33). Concurrently, these different formats were evaluated in terms of their relative influence. Absolute frequencies were relatively more persuasive for smaller magnitudes (e.g. 2.7 million) but less persuasive for larger magnitudes (e.g. 267 million), as compared to analogous presentations. Single-event probabilities were judged to minimize the significance of information. [ABSTRACT FROM AUTHOR]