# A melhor ferramenta para a sua pesquisa, trabalho e TCC!

Página 1 dos resultados de 2344 itens digitais encontrados em 0.020 segundos

## Primitive Recursive Presentations of Automata and their Products

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

56.11%

#Computer Science - Formal Languages and Automata Theory#Computer Science - Logic in Computer Science

Methods for specifying Moore type state machines (transducers) abstractly via
primitive recursive functions and for defining parallel composition via
simultaneous primitive recursion are discussed. The method is mostly of
interest as a concise and convenient way of working with the complex state
systems found in computer programming and engineering, but a short section
indicates connections to algebraic automata theory and the theorem of Krohn and
Rhodes.; Comment: 11 pages

Link permanente para citações:

## Proceedings First Symposium on Games, Automata, Logic, and Formal Verification

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 09/06/2010
Português

Relevância na Pesquisa

56.24%

#Computer Science - Computer Science and Game Theory#Computer Science - Formal Languages and Automata Theory#Computer Science - Logic in Computer Science#F.1.1#F.4.1#F.3.1#F.4.3

This volume contains the Proceedings of the first Symposium on "Games,
Automata, Logic, and Formal Verification (GandALF)", held in Minori (Amalfi
coast), Italy, 17-18 June 2010. The symposium has been promoted by a number of
Italian computer scientists interested in game theory, mathematical logic,
automata theory, and their applications to the specification, design, and
verification of complex systems. It covers a large spectrum of research topics,
ranging from theoretical aspects to concrete applications. Its aim is to
provide a forum where people from different areas, and possibly with a
different background, can successfully interact. The high-level international
profile of the event is witnessed by the composition of the program committee
and by the final program.

Link permanente para citações:

## Some Problems in Automata Theory Which Depend on the Models of Set Theory

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 14/08/2011
Português

Relevância na Pesquisa

56.22%

#Computer Science - Formal Languages and Automata Theory#Computer Science - Computational Complexity#Computer Science - Logic in Computer Science#Mathematics - Logic

We prove that some fairly basic questions on automata reading infinite words
depend on the models of the axiomatic system ZFC. It is known that there are
only three possibilities for the cardinality of the complement of an
omega-language $L(A)$ accepted by a B\"uchi 1-counter automaton $A$. We prove
the following surprising result: there exists a 1-counter B\"uchi automaton $A$
such that the cardinality of the complement $L(A)^-$ of the omega-language
$L(A)$ is not determined by ZFC: (1). There is a model $V_1$ of ZFC in which
$L(A)^-$ is countable. (2). There is a model $V_2$ of ZFC in which $L(A)^-$ has
cardinal $2^{\aleph_0}$. (3). There is a model $V_3$ of ZFC in which $L(A)^-$
has cardinal $\aleph_1$ with $\aleph_0<\aleph_1<2^{\aleph_0}$. We prove a very
similar result for the complement of an infinitary rational relation accepted
by a 2-tape B\"uchi automaton $B$. As a corollary, this proves that the
Continuum Hypothesis may be not satisfied for complements of 1-counter
omega-languages and for complements of infinitary rational relations accepted
by 2-tape B\"uchi automata. We infer from the proof of the above results that
basic decision problems about 1-counter omega-languages or infinitary rational
relations are actually located at the third level of the analytical hierarchy.
In particular...

Link permanente para citações:

## Proceedings Fourth International Symposium on Games, Automata, Logics and Formal Verification

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 16/07/2013
Português

Relevância na Pesquisa

56.24%

#Computer Science - Computer Science and Game Theory#Computer Science - Formal Languages and Automata Theory#Computer Science - Logic in Computer Science

This volume contains the proceedings of the Fourth International Symposium on
Games, Automata, Logic and Formal Verification (GandALF 2013). The symposium
took place in Borca di Cadore, Italy, from 29th to 31st of August 2013.
The proceedings of the symposium contain the abstracts of three invited talks
and 17 papers that were accepted after a careful evaluation for presentation at
the conference. The topics of the accepted papers range over a wide spectrum,
including algorithmic and behavioral game theory, game semantics, formal
languages and automata theory, modal and temporal logics, software
verification, hybrid systems.

Link permanente para citações:

## Automata theory in nominal sets

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

66.22%

#Computer Science - Logic in Computer Science#Computer Science - Formal Languages and Automata Theory

We study languages over infinite alphabets equipped with some structure that
can be tested by recognizing automata. We develop a framework for studying such
alphabets and the ensuing automata theory, where the key role is played by an
automorphism group of the alphabet. In the process, we generalize nominal sets
due to Gabbay and Pitts.

Link permanente para citações:

## On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

56.11%

Cerny's conjecture is a longstanding open problem in automata theory. We
study two different concepts, which allow to approach it from a new angle. The
first one is the triple rendezvous time, i.e., the length of the shortest word
mapping three states onto a single one. The second one is the synchronizing
probability function of an automaton, a recently introduced tool which
reinterprets the synchronizing phenomenon as a two-player game, and allows to
obtain optimal strategies through a Linear Program.
Our contribution is twofold. First, by coupling two different novel
approaches based on the synchronizing probability function and properties of
linear programming, we obtain a new upper bound on the triple rendezvous time.
Second, by exhibiting a family of counterexamples, we disprove a conjecture on
the growth of the synchronizing probability function. We then suggest natural
follow-ups towards Cernys conjecture.; Comment: A preliminary version of the results has been presented at the
conference LATA 2015. The current ArXiv version includes the most recent
improvement on the triple rendezvous time upper bound as well as formal
proofs of all the results

Link permanente para citações:

## On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

56.29%

This paper addresses the torsion problem for a class of automaton semigroups,
defined as semigroups of transformations induced by Mealy automata, aka
letter-by-letter transducers with the same input and output alphabet. The
torsion problem is undecidable for automaton semigroups in general, but is
known to be solvable within the well-studied class of (semi)groups generated by
invertible bounded Mealy automata. We focus on the somehow antipodal class of
invertible reversible Mealy automata and prove that for a wide subclass the
generated semigroup is torsion-free.; Comment: 12 pages, 4 figures, LATA'15 : 9th International Conference on
Language and Automata Theory and Applications

Link permanente para citações:

## A theory of probabilistic automata, part 1

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 18/07/2015
Português

Relevância na Pesquisa

56.15%

In the book we present main concepts of probabilistic automata theory.; Comment: 123 pages, in Russian

Link permanente para citações:

## Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 23/09/2015
Português

Relevância na Pesquisa

56.22%

#Computer Science - Logic in Computer Science#Computer Science - Formal Languages and Automata Theory

This volume contains the proceedings of the Sixth International Symposium on
Games, Automata, Logic and Formal Verification (GandALF 2015). The symposium
took place in Genoa, Italy, on the 21st and 22nd of September 2015. The
proceedings of the symposium contain the abstracts of three invited talks and
13 papers that were accepted after a careful evaluation for presentation at the
conference. The topics of the accepted papers cover algorithmic game theory,
automata theory, formal verification, and modal and temporal logics.

Link permanente para citações:

## On the state complexity of semi-quantum finite automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

56.29%

Some of the most interesting and important results concerning quantum finite
automata are those showing that they can recognize certain languages with
(much) less resources than corresponding classical finite automata
\cite{Amb98,Amb09,AmYa11,Ber05,Fre09,Mer00,Mer01,Mer02,Yak10,ZhgQiu112,Zhg12}.
This paper shows three results of such a type that are stronger in some sense
than other ones because (a) they deal with models of quantum automata with very
little quantumness (so-called semi-quantum one- and two-way automata with one
qubit memory only); (b) differences, even comparing with probabilistic
classical automata, are bigger than expected; (c) a trade-off between the
number of classical and quantum basis states needed is demonstrated in one case
and (d) languages (or the promise problem) used to show main results are very
simple and often explored ones in automata theory or in communication
complexity, with seemingly little structure that could be utilized.; Comment: 19 pages. We improve (make stronger) the results in section 3

Link permanente para citações:

## Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 13/06/2011
Português

Relevância na Pesquisa

56.25%

We study the recognition of R-trivial idempotent (R1) languages by various
models of "decide-and-halt" quantum finite automata (QFA) and probabilistic
reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model
which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from
algebraic automata theory and systems of linear inequalities to give a complete
characterization of R1 languages recognized by all these models. We also find
that "forbidden constructions" known so far do not include all of the languages
that cannot be recognized by measure-many QFA.; Comment: 30 pages, 3 figures

Link permanente para citações:

## Two-Way Finite Automata: Old and Recent Results

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 13/08/2012
Português

Relevância na Pesquisa

56.29%

#Computer Science - Formal Languages and Automata Theory#Computer Science - Computational Complexity#F.1.1#F.1.2#F.1.3

The notion of two-way automata was introduced at the very beginning of
automata theory. In 1959, Rabin and Scott and, independently, Shepherdson,
proved that these models, both in the deterministic and in the nondeterministic
versions, have the same power of one-way automata, namely, they characterize
the class of regular languages.
In 1978, Sakoda and Sipser posed the question of the cost, in the number of
the states, of the simulation of one-way and two-way nondeterministic automata
by two-way deterministic automata. They conjectured that these costs are
exponential. In spite of all attempts to solve it, this question is still open.
In the last ten years the problem of Sakoda and Sipser was widely
reconsidered and many new results related to it have been obtained. In this
work we discuss some of them. In particular, we focus on the restriction to the
unary case and on the connections with open questions in space complexity.; Comment: In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

Link permanente para citações:

## Classical automata on promise problems

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

56.34%

#Computer Science - Formal Languages and Automata Theory#Computer Science - Computational Complexity

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. Second, despite of the existing quadratic gap between Las Vegas
realtime probabilistic automata and one-way deterministic automata for language
recognition, we show that, by turning to promise problems, the tight gap
becomes exponential. Last, we show that the situation is different for one-way
probabilistic automata with two-sided bounded-error. We present a family of
unary promise problems that is very easy for these machines; solvable with only
two states, but the number of states in two-way alternating or any simpler
automata is not limited by a constant. Moreover...

Link permanente para citações:

## Graph Spectral Properties of Deterministic Finite Automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 11/05/2014
Português

Relevância na Pesquisa

56.18%

We prove that a minimal automaton has a minimal adjacency matrix rank and a
minimal adjacency matrix nullity using equitable partition (from graph spectra
theory) and Nerode partition (from automata theory). This result naturally
introduces the notion of matrix rank into a regular language L, the minimal
adjacency matrix rank of a deterministic automaton that recognises L. We then
define and focus on rank-one languages: the class of languages for which the
rank of minimal automaton is one. We also define the expanded canonical
automaton of a rank-one language.; Comment: This paper has been accepted at the following conference: 18th
International Conference on Developments in Language Theory (DLT 2014),
August 26 - 29, 2014, Ekaterinburg, Russia

Link permanente para citações:

## Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/08/2014
Português

Relevância na Pesquisa

56.24%

#Computer Science - Computer Science and Game Theory#Computer Science - Formal Languages and Automata Theory#Computer Science - Logic in Computer Science#F.4.1#F.4.3#F.1.1#D.2.4

This volume contains the proceedings of the Fifth International Symposium on
Games, Automata, Logic and Formal Verification (GandALF 2014). The symposium
took place in Verona, Italy, from 10th to 12th of September 2014. The
proceedings of the symposium contain the abstracts of three invited talks and
19 papers that were accepted after a careful evaluation for presentation at the
conference. The topics of the accepted papers range over a wide spectrum,
including algorithmic and behavioral game theory, game semantics, formal
languages and automata theory, modal and temporal logics, software
verification, hybrid systems.

Link permanente para citações:

## Functional Automata - Formal Languages for Computer Science Students

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 16/12/2014
Português

Relevância na Pesquisa

56.15%

An introductory formal languages course exposes advanced undergraduate and
early graduate students to automata theory, grammars, constructive proofs,
computability, and decidability. Programming students find these topics to be
challenging or, in many cases, overwhelming and on the fringe of Computer
Science. The existence of this perception is not completely absurd since
students are asked to design and prove correct machines and grammars without
being able to experiment nor get immediate feedback, which is essential in a
learning context. This article puts forth the thesis that the theory of
computation ought to be taught using tools for actually building computations.
It describes the implementation and the classroom use of a library, FSM,
designed to provide students with the opportunity to experiment and test their
designs using state machines, grammars, and regular expressions. Students are
able to perform random testing before proceeding with a formal proof of
correctness. That is, students can test their designs much like they do in a
programming course. In addition, the library easily allows students to
implement the algorithms they develop as part of the constructive proofs they
write. Providing students with this ability ought to be a new trend in the
formal languages classroom.; Comment: In Proceedings TFPIE 2014...

Link permanente para citações:

## One-Way Reversible and Quantum Finite Automata with Advice

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

56.25%

#Quantum Physics#Computer Science - Computational Complexity#Computer Science - Formal Languages and Automata Theory

We examine the characteristic features of reversible and quantum computations
in the presence of supplementary external information, known as advice. In
particular, we present a simple, algebraic characterization of languages
recognized by one-way reversible finite automata augmented with deterministic
advice. With a further elaborate argument, we prove a similar but slightly
weaker result for bounded-error one-way quantum finite automata with advice.
Immediate applications of those properties lead to containments and separations
among various language families when they are assisted by appropriately chosen
advice. We further demonstrate the power and limitation of randomized advice
and quantum advice when they are given to one-way quantum finite automata.; Comment: A4, 10pt, 1 figure, 31 pages. This is a complete version of an
extended abstract appeared in the Proceedings of the 6th International
Conference on Language and Automata Theory and Applications (LATA 2012),
March 5-9, 2012, A Coruna, Spain, Lecture Notes in Computer Science,
Springer-Verlag, Vol.7183, pp.526-537, 2012

Link permanente para citações:

## Automata Theory Meets Barrier Certificates: Temporal Logic Verification of Nonlinear Systems

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 14/03/2014
Português

Relevância na Pesquisa

56.17%

#Computer Science - Formal Languages and Automata Theory#Computer Science - Logic in Computer Science

We consider temporal logic verification of (possibly nonlinear) dynamical
systems evolving over continuous state spaces. Our approach combines
automata-based verification and the use of so-called barrier certificates.
Automata-based verification allows the decomposition the verification task into
a finite collection of simpler constraints over the continuous state space. The
satisfaction of these constraints in turn can be (potentially conservatively)
proved by appropriately constructed barrier certificates. As a result, our
approach, together with optimization-based search for barrier certificates,
allows computational verification of dynamical systems against temporal logic
properties while avoiding explicit abstractions of the dynamics as commonly
done in literature.

Link permanente para citações:

## Decidability of minimization of fuzzy automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 18/05/2013
Português

Relevância na Pesquisa

56.29%

State minimization is a fundamental problem in automata theory. The problem
is also of great importance in the study of fuzzy automata. However, most work
in the literature considered only state reduction of fuzzy automata, whereas
the state minimization problem is almost untouched for fuzzy automata. Thus in
this paper we focus on the latter problem. Formally, the decision version of
the minimization problem of fuzzy automata is as follows: \begin{itemize}
\item Given a fuzzy automaton $\mathcal{A}$ and a natural number $k$, that
is, a pair $\langle \mathcal{A}, k\rangle$, is there a $k$-state fuzzy
automaton equivalent to $\mathcal{A}$? \end{itemize} We prove for the first
time that the above problem is decidable for fuzzy automata over totally
ordered lattices. To this end, we first give the concept of systems of fuzzy
polynomial equations and then present a procedure to solve these systems.
Afterwards, we apply the solvability of a system of fuzzy polynomial equations
to the minimization problem mentioned above, obtaining the decidability.
Finally, we point out that the above problem is at least as hard as
PSAPCE-complete.; Comment: 20pages, comments are welcome

Link permanente para citações:

## Hankel Matrices for Weighted Visibly Pushdown Automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 08/12/2015
Português

Relevância na Pesquisa

56.28%

Hankel matrices (aka connection matrices) of word functions and graph
parameters have wide applications in automata theory, graph theory, and machine
learning. We give a characterization of real-valued functions on nested words
recognized by weighted visibly pushdown automata in terms of Hankel matrices on
nested words. This complements C. Mathissen's characterization in terms of
weighted monadic second order logic.; Comment: Accepted for publication in the 10th International Conference on
Language and Automata Theory and Applications (LATA 2016)

Link permanente para citações: