Search results for "computational complexity."
showing 10 items of 245 documents
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata
2018
In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
Tally languages accepted by Monte Carlo pushdown automata
1997
Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.
The computational power of continuous time neural networks
1997
We investigate the computational power of continuous-time neural networks with Hopfield-type units. We prove that polynomial-size networks with saturated-linear response functions are at least as powerful as polynomially space-bounded Turing machines.
Performance comparison of residual related algorithms for ToA positioning in wireless terrestrial and sensor networks
2009
©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE." Article also available from publisher: http://dx.doi.org/10.1109/WIRELESSVITAE.2009.5172462 Time of Arrival (ToA) is a popular technique for terrestrial positioning. This paper presents a comparison of ToA based residual related positioning algorithms in wireless terrestrial and sensor networks in both long range outdoor and short range indoor environments. Us…
Hamiltonian structural analysis of curved beams with or without generalized two-parameter foundation
2013
The solution of curved Timoshenko beams with or without generalized two-parameter elastic foundation is presented. Beam can be subjected to any kind of loads and imposed external actions, distributed or concentrated along the beam. It can have external and internal restraints and any kind of internal kinematical or mechanical discontinuity. Moreover, the beam may have any spatial curved geometry, by dividing the entire structure into segments of constant curvature and constant elastic properties, each segment resting or not on elastic foundation. The foundation has six parameters like a generalized Winkler soil with the addition of other two parameters involving the link between settlements…
Multi-label Classification Using Stacked Hierarchical Dirichlet Processes with Reduced Sampling Complexity
2018
Nonparametric topic models based on hierarchical Dirichlet processes (HDPs) allow for the number of topics to be automatically discovered from the data. The computational complexity of standard Gibbs sampling techniques for model training is linear in the number of topics. Recently, it was reduced to be linear in the number of topics per word using a technique called alias sampling combined with Metropolis Hastings (MH) sampling. We propose a different proposal distribution for the MH step based on the observation that distributions on the upper hierarchy level change slower than the document-specific distributions at the lower level. This reduces the sampling complexity, making it linear i…
Two-variable First-Order Logic with Counting in Forests
2018
We consider an extension of two-variable, first-order logic with counting quantifiers and arbitrarily many unary and binary predicates, in which one distinguished predicate is interpreted as the mother-daughter relation in an unranked forest. We show that both the finite satisfiability and the general satisfiability problems for the extended logic are decidable in NExpTime. We also show that the decision procedure for finite satisfiability can be extended to the logic where two distinguished predicates are interpreted as the mother-daughter relations in two independent forests.
Chromatic sums for colorings avoiding monochromatic subgraphs
2015
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
Some Computational Aspects of DISTANCE-SAT
2007
In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones …
Inverse Tone Mapping Based upon Retina Response
2014
International audience; The development of high dynamic range (HDR) display arouses the research of inverse tone mapping methods, which expand dynamic range of the low dynamic range (LDR) image to match that of HDR monitor. This paper proposed a novel physiological approach, which could avoid artifacts occurred in most existing algorithms. Inspired by the property of the human visual system (HVS), this dynamic range expansion scheme performs with a low computational complexity and a limited number of parameters and obtains high-quality HDR results. Comparisons with three recent algorithms in the literature also show that the proposed method reveals more important image details and produces …