Search results for "Automaton"

Concrete syntax-based find for graphical DSLs

2020

There are services available in the most software tools we have got used to like, copy, paste, cut, find, and replace. However, the state of the art is not so good with tools of graphical languages. Even many commercial modelling tools have limited support of the find feature. We propose to add find as a service of graphical DSL tool development frameworks. This way find is available in any DSL built using the DSL tool development framework. The concrete syntax-based find has been implemented as a service of the DSL tool development framework ajoo. Two graph-based languages: UML Activity diagrams and Deterministic Finite Automata (DFA) transition diagrams are used to demonstrate usage of th…

A cellular automaton based model simulating HVAC fluid and heat transport in a building. Modeling approach and comparison with experimental results

2010

A discrete model characterizing heat and fluid flow in connection with thermal fluxes in a building is described and tested against experiment in this contribution. The model, based on a cellular automaton approach, relies on a set of a few quite simple rules and parameters in order to simulate the dynamic evolution of temperatures and energy flows in any water or brine based thermal energy distribution network in a building or system. Using an easy-to-record input, such as the instantaneous electrical power demand of the heating or cooling system, our model predicts time varying temperatures in characteristic spots and the related enthalpy flows whose simulation usually requires heavy comp…

Moore Automata and Epichristoffel Words

2012

Visibly pushdown modular games,

2014

Games on recursive game graphs can be used to reason about the control flow of sequential programs with recursion. In games over recursive game graphs, the most natural notion of strategy is the modular strategy, i.e., a strategy that is local to a module and is oblivious to previous module invocations, and thus does not depend on the context of invocation. In this work, we study for the first time modular strategies with respect to winning conditions that can be expressed by a pushdown automaton. We show that such games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state automat…

Computational Limitations of Affine Automata

2019

We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-values affine automata is simulated in logarithmic space. Second, we give an impossibility result for algebraic-valued affine automata. As a result, we identify some unary languages (in logarithmic space) that are not recognized by algebraic-valued affine automata with cutpoints.

Quantum, stochastic, and pseudo stochastic languages with few states

2014

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all th…

The Descriptive Complexity Approach to LOGCFL

1998

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…

New Results on Vector and Homing Vector Automata

2019

We present several new results and connections between various extensions of finite automata through the study of vector automata and homing vector automata. We show that homing vector automata outperform extended finite automata when both are defined over $ 2 \times 2 $ integer matrices. We study the string separation problem for vector automata and demonstrate that generalized finite automata with rational entries can separate any pair of strings using only two states. Investigating stateless homing vector automata, we prove that a language is recognized by stateless blind deterministic real-time version of finite automata with multiplication iff it is commutative and its Parikh image is …

Superiority of exact quantum automata for promise problems

2011

In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.

Classical automata on promise problems

2015

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Secon…