22 results on '"*AMBIGUITY"'
Search Results
2. Weighted Derivation Trees.
- Author
-
Loui, Michael C.
- Subjects
- *
COMBINATORIAL optimization , *GRAMMAR , *COMPUTATIONAL complexity , *ELECTRONIC data processing , *MACHINE theory , *COMPUTER software - Abstract
The nodes of a weighted derivation tree are associated with weighting functions over the vocabulary of a context-free grammar. An algorithm is presented for constructing the optimal derivation tree having the same structure as a given weighted derivation tree. In addition, the correctness of the algorithm is established. The method may be applied to problems involving probabilistic parsing or combinatorial optimization. [ABSTRACT FROM AUTHOR]
- Published
- 1976
- Full Text
- View/download PDF
3. On Determinism and Unambiguity of Weighted Two-Way Automata.
- Author
-
Carnino, Vincent and Lombardy, Sylvain
- Subjects
- *
MACHINE theory , *MATHEMATICAL proofs , *POWER series , *SEMIRINGS (Mathematics) , *COMMUTATIVE rings - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
4. Descriptional complexity of unambiguous input-driven pushdown automata.
- Author
-
Okhotin, Alexander and Salomaa, Kai
- Subjects
- *
COMPUTATIONAL complexity , *MACHINE theory , *MATHEMATICAL transformations , *DETERMINISTIC algorithms , *HOMOMORPHISMS - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
5. Ambiguity and structural ambiguity of symmetric difference NFAs.
- Author
-
van der Merwe, A.B., van Zijl, L., and Geldenhuys, J.
- Subjects
- *
AMBIGUITY , *MACHINE theory , *FINITE state machines , *COMPUTER systems , *INFORMATION technology , *LINEAR systems - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
6. UNAMBIGUOUS CONSTRAINED AUTOMATA.
- Author
-
CADILHAC, MICHAËL, FINKEL, ALAIN, and MCKENZIE, PIERRE
- Subjects
- *
MACHINE theory , *PROGRAMMING languages , *PROBLEM solving , *MATHEMATICAL bounds , *SELF-expression - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
7. Ambiguity and Communication.
- Author
-
Hromkovič, Juraj and Schnitger, Georg
- Subjects
- *
AMBIGUITY , *MACHINE theory , *NUMBER theory , *FORMAL languages , *COMMUNICATION , *NATURAL numbers , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
8. Deterministic recognizability of picture languages with Wang automata.
- Author
-
Lonati, Violetta and Pradella, Matteo
- Subjects
- *
ROBOTS , *MACHINE theory , *COMPUTER assisted instruction , *LANGUAGE & languages , *SCANNING systems - Abstract
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]
- Published
- 2010
9. Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages.
- Author
-
Anselmo, Marcella, Giammarresi, Dora, and Madonia, Maria
- Subjects
- *
MACHINE theory , *FORMAL languages , *LANGUAGE & languages , *IMAGE processing , *COMPARATIVE grammar - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF
10. Deterministic and unambiguous two-dimensional languages over one-letter alphabet
- Author
-
Anselmo, Marcella and Madonia, Maria
- Subjects
- *
ONE-letter words , *SEQUENTIAL machine theory , *PROGRAMMING languages , *TESSELLATIONS (Mathematics) , *MACHINE theory - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
11. Optimal Number and Locations of Power Quality Monitors Considering System Topology.
- Author
-
Dong-Jun Won and Seung-Il Moon
- Subjects
- *
INFORMATION display systems , *COMPUTER monitors , *TOPOLOGY , *ALGORITHMS , *GRAPH theory , *MATRICES (Mathematics) , *TECHNICAL specifications , *SEMANTICS , *MACHINE theory - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
12. AMBIGUITY BY RESTARTING AUTOMATA.
- Author
-
MRÁZ, FRANTIŠEK, PLÁTEK, MARTIN, JURDZIŃSKI, TOMASZ, and Truthe, B.
- Subjects
- *
MACHINE theory , *REWRITING systems (Computer science) , *AMBIGUITY , *LANGUAGE & logic , *LINEAR programming , *RECURSIVE functions - Abstract
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]
- Published
- 2007
13. One-unambiguity of regular expressions with numeric occurrence indicators
- Author
-
Kilpeläinen, Pekka and Tuhkanen, Rauno
- Subjects
- *
XML (Extensible Markup Language) , *MACHINE theory , *COMPUTABLE functions , *MATHEMATICAL models - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
14. Characterizations of recognizable picture series
- Author
-
Mäurer, Ina
- Subjects
- *
LANGUAGE & languages , *IMAGE processing , *POWER series , *MACHINE theory , *PICTURES - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
15. Interpreted Trajectories.
- Author
-
Domaratzki, Michael, Rozenberg, Grzegorz, and Salomaa, Kai
- Subjects
- *
MACHINE theory , *TURING machines , *QUANTUM trajectories , *DECIDABILITY (Mathematical logic) , *MATHEMATICS - Abstract
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]
- Published
- 2006
16. Sublogarithmic ambiguity
- Author
-
Wich, Klaus
- Subjects
- *
MACHINE theory , *ARTIFICIAL intelligence , *SEMANTICS , *COMPUTABLE functions - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
17. Development of a deterministic XML schema by resolving structure ambiguity of HL7 messages
- Author
-
Huang, Ean-Wen, Wang, Da-Wei, and Liou, Der-Ming
- Subjects
- *
XML (Extensible Markup Language) , *HYPERTEXT systems , *MACHINE theory , *MEDICAL care - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
18. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
- Author
-
Klimann, Ines, Lombardy, Sylvain, Mairesse, Jean, and Prieur, Christophe
- Subjects
- *
ROBOTS , *SEQUENTIAL machine theory , *MACHINE theory , *ROBOTICS - Abstract
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]
- Published
- 2004
- Full Text
- View/download PDF
19. Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
- Author
-
Homan, Christopher M.
- Subjects
- *
COMPUTATIONAL complexity , *ELECTRONIC data processing , *MACHINE theory , *SEMANTICS - Abstract
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 everyd∈N+ , there is anO(log -to-one, strong, total, associative, one-way function1 /d n)σ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 inPolylogP if there exists a polynomial-time Turing machineM accepting the language such that for somed∈R+ it holds thatM has on each stringx at mostO(logd n) accepting paths, wheren=|x| . We show thatP≠PolylogP if and only for somed∈R+ there exists anO(logd n) -to-one, strong, total, associative, one-way function. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
20. Ambiguity in omega context free languages
- Author
-
Finkel, Olivier
- Subjects
- *
AMBIGUITY , *MACHINE theory - Abstract
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]- Published
- 2003
- Full Text
- View/download PDF
21. Which Statistical Formats Facilitate What Decisions? The Perception and Influence of Different Statistical Information Formats.
- Author
-
Brase, Gary L.
- Subjects
PROBABILITY theory ,STATISTICS ,COMPUTATIONAL complexity ,ELECTRONIC data processing ,MACHINE theory - Abstract
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]
- Published
- 2002
- Full Text
- View/download PDF
22. Synthesis of Inference-Based Decentralized Control for Discrete Event Systems.
- Author
-
Takai, Shigemasa and Kumar, Ratnesh
- Subjects
- *
DISCRETE-time systems , *DIGITAL control systems , *SYSTEM analysis , *OBSERVABILITY (Control theory) , *CONTROL theory (Engineering) , *SUBLANGUAGE , *COMPUTATIONAL complexity , *MACHINE theory , *AUTOMATIC control systems - Abstract
In our past work, we presented a framework for the decentralized control of discrete event systems involving inferencing over ambiguities, about the system state, of various local decision makers. Using the knowledge of the self-ambiguity and those of the others, each local control decision is tagged with a certain ambiguity level (level zero being the minimum and representing no ambiguity). A global control decision is taken to be a "winning" local control decision, i.e., one with a minimum ambiguity level. For the existence of a decentralized supervisor, so that for each controllable event the ambiguity levels of all winning disablement or enablement decisions are bounded by some number N (such a supervisor is termed N-inferring), the notion of Ninference-observability was introduced. When the given specification fails to satisfy the N-inference-observability property, an N-inferring supervisor achieving the entire specification does not exist. We first show that the class of N-inference-observable sublanguages is not closed under union implying that the supremal Ninference-observable sublanguage need not exist. We next provide a technique for synthesizing an N-inferring decentralized supervisor that achieves an N-inference-observable sublanguage of the specification. The sublanguage achieved equals the specification language when the specification itself is N-inference-observable. A formula for the synthesized sublanguage is also presented. For the special cases of N = 0 and N = 1, the proposed supervisor achieves the same language as those reported in [25], [31] (for N = 0) and [32] (for N = 1). The synthesized supervisor is parameterized by N (the parameter bounding the ambiguity level), and as N is increased, the supervisor becomes strictly more permissive in general. Thus, a user can choose N based on the degree of permissiveness and the degree of computational complexity desired. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.