ID: 1507.05164

A theory of probabilistic automata, part 1

July 18, 2015

View on ArXiv

Similar papers 2

Convex Language Semantics for Nondeterministic Probabilistic Automata

May 29, 2018

88% Match
Heerdt Gerco van, Justin Hsu, ... , Silva Alexandra
Formal Languages and Automat...
Logic in Computer Science

We explore language semantics for automata combining probabilistic and nondeterministic behavior. We first show that there are precisely two natural semantics for probabilistic automata with nondeterminism. For both choices, we show that these automata are strictly more expressive than deterministic probabilistic automata, and we prove that the problem of checking language equivalence is undecidable by reduction from the threshold problem. However, we provide a discounted met...

Find SimilarView on arXiv

Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability

July 28, 2009

88% Match
Christel Technische Universität Dresden Baier, Nathalie INRIA Rennes Bertrand, Marcus Technische Universität Dresden Größer
Formal Languages and Automat...

Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) the probability for the accepting runs is positive (probable semantics), or (ii) almost all runs are accepting (almost-sure semantics), or (iii) the probability measure of the accepting runs is greater than a certain threshold (thresh...

Find SimilarView on arXiv

Mathematical Approach in Automata and Automata Association

November 16, 2020

88% Match
Sergio Henrique Maciel
Formal Languages and Automat...

The transition structure of an automaton can be used to create a natural topology to the set of states of an automaton, generating, this way, a topological space. Probabilistic automata can also be modeled in terms of measure theory. A system of many automata would be reduced to simple mathematical structures and analyzed by a topological point of view.

Find SimilarView on arXiv

Automaton (Semi)groups (Basic Concepts)

January 29, 2018

88% Match
Jānis Buls, Līga Užule, Aigars Valainis
Group Theory

In this paper, we give an introduction to basic concepts of automaton semigroups. While we must note that this paper does not contain new results, it is focused on extended introduction in the subject and detailed examples.

Find SimilarView on arXiv

Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time

May 2, 2012

87% Match
Holger Hermanns, Andrea Turrini
Formal Languages and Automat...

Deciding in an efficient way weak probabilistic bisimulation in the context of Probabilistic Automata is an open problem for about a decade. In this work we close this problem by proposing a procedure that checks in polynomial time the existence of a weak combined transition satisfying the step condition of the bisimulation. We also present several extensions of weak combined transitions, such as hyper-transitions and the new concepts of allowed weak combined and hyper-transi...

Find SimilarView on arXiv

Foundations of Probability Theory for AI - The Application of Algorithmic Probability to Problems in Artificial Intelligence

March 27, 2013

87% Match
Ray Solomonoff
Artificial Intelligence

This paper covers two topics: first an introduction to Algorithmic Complexity Theory: how it defines probability, some of its characteristic properties and past successful applications. Second, we apply it to problems in A.I. - where it promises to give near optimum search procedures for two very broad classes of problems.

Find SimilarView on arXiv

Computations in Stochastic Acceptors

December 23, 2018

87% Match
Karl-Heinz Zimmermann
Machine Learning
Machine Learning

Machine learning provides algorithms that can learn from data and make inferences or predictions on data. Stochastic acceptors or probabilistic automata are stochastic automata without output that can model components in machine learning scenarios. In this paper, we provide dynamic programming algorithms for the computation of input marginals and the acceptance probabilities in stochastic acceptors. Furthermore, we specify an algorithm for the parameter estimation of the cond...

Find SimilarView on arXiv

Probabilistic Automata for Computing with Words

April 23, 2006

87% Match
Yongzhi Cao, Lirong Xia, Mingsheng Ying
Artificial Intelligence
Computation and Language

Usually, probabilistic automata and probabilistic grammars have crisp symbols as inputs, which can be viewed as the formal models of computing with values. In this paper, we first introduce probabilistic automata and probabilistic grammars for computing with (some special) words in a probabilistic framework, where the words are interpreted as probabilistic distributions or possibility distributions over a set of crisp symbols. By probabilistic conditioning, we then establish ...

Find SimilarView on arXiv

What is known about the Value 1 Problem for Probabilistic Automata?

October 13, 2014

87% Match
Nathanaël LIAFA Fijalkow
Formal Languages and Automat...

The value 1 problem is a decision problem for probabilistic automata over finite words: are there words accepted by the automaton with arbitrarily high probability? Although undecidable, this problem attracted a lot of attention over the last few years. The aim of this paper is to review and relate the results pertaining to the value 1 problem. In particular, several algorithms have been proposed to partially solve this problem. We show the relations between them, leading to ...

Find SimilarView on arXiv

On the Theory of Stochastic Automata

March 26, 2021

87% Match
Merve Nur Cakir, Mehwish Saleemi, Karl-Heinz Zimmermann
Formal Languages and Automat...
Computation and Language
Probability

The theory of discrete stochastic systems has been initiated by the work of Shannon and von Neumann. While Shannon has considered memory-less communication channels and their generalization by introducing states, von Neumann has studied the synthesis of reliable systems from unreliable components. The fundamental work of Rabin and Scott about deterministic finite-state automata has led to two generalizations. First, the generalization of transition functions to conditional di...

Find SimilarView on arXiv