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

Primitive Recursive Presentations of Automata and their Products

Yodaiken, Victor
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
56.11%
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

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

Montanari, Angelo; Napoli, Margherita; Parente, Mimmo
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%
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.

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

Finkel, Olivier
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%
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...

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

Puppis, Gabriele; Villa, Tiziano
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%
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.

Automata theory in nominal sets

Bojańczyk, Mikołaj; Klin, Bartek; Lasota, Sławomir
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
66.22%
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.

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

Gonze, François; Jungers, Raphaël M.
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

On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata

Godin, Thibault; Klimann, Ines; Picantin, Matthieu
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

A theory of probabilistic automata, part 1

Mironov, Andrew M.
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

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

Esparza, Javier; Tronci, Enrico
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%
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.

On the state complexity of semi-quantum finite automata

Zheng, Shenggen; Gruska, Jozef; Qiu, Daowen
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

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

Golovkins, Marats; Kravtsev, Maksim; Kravcevs, Vasilijs
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

Two-Way Finite Automata: Old and Recent Results

Pighizzini, Giovanni
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%
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

Classical automata on promise problems

Geffert, Viliam; Yakaryilmaz, Abuzer
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
56.34%
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...

Graph Spectral Properties of Deterministic Finite Automata

Sin'ya, Ryoma
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

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

Peron, Adriano; Piazza, Carla
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%
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.

Functional Automata - Formal Languages for Computer Science Students

Morazán, Marco T.; Antunez, Rosario
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...

One-Way Reversible and Quantum Finite Automata with Advice

Yamakami, Tomoyuki
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
56.25%
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

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

Wongpiromsarn, Tichakorn; Topcu, Ufuk; Lamperski, Andrew
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%
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.

Decidability of minimization of fuzzy automata

Li, Lvzhou; Qiu, Daowen
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

Hankel Matrices for Weighted Visibly Pushdown Automata

Labai, Nadia; Makowsky, Johann A.
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)