Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImage-Binary Automata
62
0
0.0
(
0
)
Added by
Cas Widdershoven
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce a certain restriction of weighted automata over the rationals, called image-binary automata. We show that such automata accept the regular languages, can be exponentially more succinct than corresponding NFAs, and allow for polynomial complementation, union, and intersection. This compares favourably with unambiguous automata whose complementation requires a superpolynomial state blowup. We also study an infinite-word version, image-binary Buchi automata. We show that such automata are amenable to probabilistic model checking, similarly to unambiguous Buchi automata. We provide algorithms to translate $k$-ambiguous Buchi automata to image-binary Buchi automata, leading to model-checking algorithms with optimal computational complexity.
rate research
Read More
We introduce homing vector automata, which are finite automata augmented by a vector that is multiplied at each step by a matrix determined by the current transition, and have to return the vector to its original setting in order to accept the input. The computational power and properties of deterministic, nondeterministic, blind, non-blind, real-time and one-w
Parikh automata extend automata with counters whose values can only be tested at the end of the computation, with respect to membership into a semi-linear set. Parikh automata have found several applications, for instance in transducer theory, as they enjoy decidable emptiness problem. In this paper, we study two-way Parikh automata. We show that emptiness becomes undecidable in the non-deterministic case. However, it is PSpace-C when the number of visits to any input position is bounded and the semi-linear set is given as an existential Presburger formula. We also give tight complexity bounds for the inclusion, equivalence and universality problems. Finally, we characterise precisely the complexity of those problems when the semi-linear constraint is given by an arbitrary Presburger formula.
In this paper we introduce and study Event-Clock Nested Automata (ECNA), a formalism that combines Event Clock Automata (ECA) and Visibly Pushdown Automata (VPA). ECNA allow to express real-time properties over non-regular patterns of recursive programs. We prove that ECNA retain the same closure and decidability properties of ECA and VPA being closed under Boolean operations and having a decidable language-inclusion problem. In particular, we prove that emptiness, universality, and language-inclusion for ECNA are EXPTIME-complete problems. As for the expressiveness, we have that ECNA properly extend any previous attempt in the literature of combining ECA and VPA.
We present an underapproximation for context-free languages by filtering out runs of the underlying pushdown automaton depending on how the stack height evolves over time. In particular, we assign to each run a number quantifying the oscillating behavior of the stack along the run. We study languages accepted by pushdown automata restricted to k-oscillating runs. We relate oscillation on pushdown automata with a counterpart restriction on context-free grammars. We also provide a way to filter all but the k-oscillating runs from a given PDA by annotating stack symbols with information about the oscillation. Finally, we study closure properties of the defined class of languages and the complexity of the k-emptiness problem asking, given a pushdown automaton P and k >= 0, whether P has a k-oscillating run. We show that, when k is not part of the input, the k-emptiness problem is NLOGSPACE-complete.
Gauge-invariance is a fundamental concept in Physics---known to provide mathematical justification for the fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts directly in terms of Cellular Automata. More precisely, the notions of gauge-invariance and gauge-equivalence in Cellular Automata are formalized. A step-by-step gauging procedure to enforce this symmetry upon a given Cellular Automaton is developed, and three examples of gauge-invariant Cellular Automata are examined.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
