Einloggen

Thematische Bibliographien / Ω-automata / Zeitschriftenartikel

Zeitschriftenartikel zum Thema „Ω-automata“

Um die anderen Arten von Veröffentlichungen zu diesem Thema anzuzeigen, folgen Sie diesem Link: Ω-automata.

Autor: Grafiati

Veröffentlicht am 25. Mai 2024

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit Top-50 Zeitschriftenartikel für die Forschung zum Thema "Ω-automata" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Sehen Sie die Zeitschriftenartikel für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.

1

Krithivasan, Kamala, K. Sharda und Sandeep V. Varma. „Distributed ω-Automata“. International Journal of Foundations of Computer Science 14, Nr. 04 (August 2003): 681–98. http://dx.doi.org/10.1142/s0129054103001959.

Der volle Inhalt der Quelle

Annotation:

In this paper, we introduce the notion of distributed ω-automata. Distributed ω-automata are a group of automata working in unison to accept an ω-language. We build the theory of distributed ω-automata for finite state automata and pushdown automata in different modes of cooperation like the t-mode, *-mode, = k-mode, ≤ k-mode and ≥ k-mode along with different acceptance criteria i.e. Büchi-, Muller-, Rabin- and Streett- acceptance criteria. We then analyze the acceptance power of such automata in all the above modes of cooperation and acceptance criteria. We present proofs that distributed ω-finite state automata do not have any additional power over ω-finite state automata in any of the modes of cooperation or acceptance criteria, while distributed ω-pushdown automata can accept languages not in CFLω. We give proofs for the equivalence of all modes of cooperation and acceptance criteria in the case of distributed ω-pushdown automata. We show that the power of distributed ω-pushdown automata is equal to that of ω-Turing Machines. We also study the deterministic version of distributed ω-pushdown automata. Deterministic ω-pushdown automata accept only languages contained in CFLω but distributed deterministic ω-pushdown automata can accept languages not in CFLω and have the same power as their nondeterministic counterparts. We also define distributed completely deterministic ω-pushdown automata and analyze their power.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Baier, Christel, Marcus Grösser und Nathalie Bertrand. „Probabilistic ω-automata“. Journal of the ACM 59, Nr. 1 (Februar 2012): 1–52. http://dx.doi.org/10.1145/2108242.2108243.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Krithivasan, Kamala, und K. Sharda. „Fuzzy ω-automata“. Information Sciences 138, Nr. 1-4 (Oktober 2001): 257–81. http://dx.doi.org/10.1016/s0020-0255(01)00150-5.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

CARNINO, VINCENT, und SYLVAIN LOMBARDY. „FACTORIZATIONS AND UNIVERSAL AUTOMATON OF OMEGA LANGUAGES“. International Journal of Foundations of Computer Science 25, Nr. 08 (Dezember 2014): 1111–25. http://dx.doi.org/10.1142/s0129054114400279.

Der volle Inhalt der Quelle

Annotation:

We extend the concept of factorization on finite words to ω-rational languages and show how to compute them. We define a normal form for Büchi automata and introduce a universal automaton for Büchi automata in normal form. We prove that, for every ω-rational language, this Büchi automaton, based on factorization, is canonical and that it is the smallest automaton that contains the morphic image of every equivalent Büchi automaton in normal form.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Lindsay, Peter A. „On alternating ω-automata“. Journal of Computer and System Sciences 36, Nr. 1 (Februar 1988): 16–24. http://dx.doi.org/10.1016/0022-0000(88)90018-9.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

KUPFERMAN, ORNA, GILA MORGENSTERN und ANIELLO MURANO. „TYPENESS FOR ω-REGULAR AUTOMATA“. International Journal of Foundations of Computer Science 17, Nr. 04 (August 2006): 869–83. http://dx.doi.org/10.1142/s0129054106004157.

Der volle Inhalt der Quelle

Annotation:

We introduce and study three notions of typeness for automata on infinite words. For an acceptance-condition class γ (that is, γ is weak, Büchi, co-Büchi, Rabin, or Streett), deterministic γ-typeness asks for the existence of an equivalent γ-automaton on the same deterministic structure, nondeterministic γ-typeness asks for the existence of an equivalent γ-automaton on the same structure, and γ-powerset-typeness asks for the existence of an equivalent γ-automaton on the (deterministic) powerset structure – one obtained by applying the subset construction. The notions are helpful in studying the complexity and complication of translations between the various classes of automata. For example, we prove that deterministic Büchi automata are co-Büchi type; it follows that a translation from deterministic Büchi to deterministic co-Büchi automata, when exists, involves no blow up. On the other hand, we prove that nondeterministic Büchi automata are not co-Büchi type; it follows that a translation from a nondeterministic Büchi to nondeterministic co-Büchi automata, when exists, should be more complicated than just redefining the acceptance condition. As a third example, by proving that nondeterministic co-Büchi automata are Büchi-powerset type, we show that a translation of nondeterministic co-Büchi to deterministic Büchi automata, when exists, can be done applying the subset construction. We give a complete picture of typeness for the weak, Büchi, co-Büchi, Rabin, and Streett acceptance conditions, and discuss its usefulness.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

Engelfriet, Joost, und Hendrik Jan Hoogeboom. „X-automata on ω-words“. Theoretical Computer Science 110, Nr. 1 (März 1993): 1–51. http://dx.doi.org/10.1016/0304-3975(93)90349-x.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

Chen, Zhe. „On the Generative Power of ω-Grammars and ω-Automata“. Fundamenta Informaticae 111, Nr. 2 (2011): 119–45. http://dx.doi.org/10.3233/fi-2011-557.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

9

Löding, Christof, und Max Philip Stachon. „On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words“. Fundamenta Informaticae 189, Nr. 1 (07.07.2023): 69–91. http://dx.doi.org/10.3233/fi-222152.

Der volle Inhalt der Quelle

Annotation:

We study minimization problems for deterministic ω-automata in the presence of don’t care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don’t care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don’t care words). We then analyze languages of don’t care words with a trivial right-congruence. For such sets of don’t care words it is known that weak deterministic Büchi automata (WDBA) have a unique minimal automaton that can be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don’t care minimization results for WDBA do not extend to deterministic ω-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don’t care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don’t care words with trivial right-congruence.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

La Torre, Salvatore, und Margherita Napoli. „Finite automata on timed ω-trees“. Theoretical Computer Science 293, Nr. 3 (Februar 2003): 479–505. http://dx.doi.org/10.1016/s0304-3975(02)00611-4.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

11

Finkel, Olivier, und Stevo Todorčević. „A hierarchy of tree-automatic structures“. Journal of Symbolic Logic 77, Nr. 1 (März 2012): 350–68. http://dx.doi.org/10.2178/jsl/1327068708.

Der volle Inhalt der Quelle

Annotation:

AbstractWe consider ωn-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length ωn for some integer n ≥ 1. We show that all these structures are ω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for ω2-automatic (resp. ωn-automatic for n > 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for ωn-automatic boolean algebras, n ≥ 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a -set nor a -set. We obtain that there exist infinitely many ωn-automatic, hence also ω-tree-automatic, atomless boolean algebras , which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14].

APA, Harvard, Vancouver, ISO und andere Zitierweisen

12

PENG, WUXU, und S. PURUSHOTHAMAN IYER. „A NEW TYPE OF PUSHDOWN AUTOMATA ON INFINITE TREES“. International Journal of Foundations of Computer Science 06, Nr. 02 (Juni 1995): 169–86. http://dx.doi.org/10.1142/s0129054195000123.

Der volle Inhalt der Quelle

Annotation:

In this paper we consider pushdown automata on infinite trees with empty stack as the accepting condition (ω-EPDTA). We provide the following regarding ω-EPDTA: (a) its relationship to other Pushdown automata on infinite trees, (b) a Kleene-Closure theorem and (c) a single exponential time algorithm for checking emptiness. We demonstrate the usefulness of ω-EPDTA through two example applications: defining the temporal uniform inevitability property and specifying a context-free process with unbounded state space, both of which cannot be defined and/or specified by the classical finite state automata on infinite trees. We also discuss the relevance of the results presented here to model-checking.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

13

Moriya, Tetsuo, und Hideki Yamasaki. „Accepting conditions for automata on ω-languages“. Theoretical Computer Science 61, Nr. 2-3 (November 1988): 137–47. http://dx.doi.org/10.1016/0304-3975(88)90121-1.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

14

Dobronravov, Egor, Nikita Dobronravov und Alexander Okhotin. „On the Length of Shortest Strings Accepted by Two-way Finite Automata“. Fundamenta Informaticae 180, Nr. 4 (30.06.2021): 315–31. http://dx.doi.org/10.3233/fi-2021-2044.

Der volle Inhalt der Quelle

Annotation:

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n− log m).

APA, Harvard, Vancouver, ISO und andere Zitierweisen

15

Carton, Olivier, und Dominique Perrin. „Chains and Superchains for ω-Rational Sets, Automata and Semigroups“. International Journal of Algebra and Computation 07, Nr. 06 (Dezember 1997): 673–95. http://dx.doi.org/10.1142/s0218196797000290.

Der volle Inhalt der Quelle

Annotation:

We introduce several equivalent notions that generalize ones introduced by Klaus Wagner for finite Muller automata under the name of chains and superchains. We define such objects in relation to ω-rational sets, Muller automata or also ω-semigroups. We prove their equivalence and derive some basic properties of these objects. In a subsequent paper, we show how these concepts allow us to derive a new presentation of the hierarchy due to K. Wagner and W. Wadge.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

16

Muhiuddin, G., K. Janaki, D. Al-Kadi, R. Arulprakasam und V. Govindan. „On Subclasses of Recognizable ω ω − Partial Array Languages“. Journal of Mathematics 2022 (12.09.2022): 1–11. http://dx.doi.org/10.1155/2022/1493126.

Der volle Inhalt der Quelle

Annotation:

In this paper, the concepts of infinite partial array languages ( ω ω − partial array languages) and the classes of ω ω − partial array languages, namely, local ω ω − partial array languages, Buchi local ω ω − partial array languages, and Muller local ω ω − partial array languages are defined, and their related properties are studied. Furthermore, we introduce nondeterministic finite online tessellation h -automata on ω ω − partial array languages. In addition, we prove that the class of all adherences of finite local partial array languages is equal to the class of all local ω ω − partial array languages and also prove that every ω ω − regular partial array language is a projection of Buchi local ω ω − partial array language.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

17

Droste, Manfred, und Werner Kuich. „A Kleene Theorem for Weighted ω-Pushdown Automata“. Acta Cybernetica 23, Nr. 1 (2017): 43–59. http://dx.doi.org/10.14232/actacyb.23.1.2017.4.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

18

Thistle, J. G., und R. P. Malhamé. „Control of ω-automata under state fairness assumptions“. Systems & Control Letters 33, Nr. 4 (April 1998): 265–74. http://dx.doi.org/10.1016/s0167-6911(97)00106-0.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

19

Tao, Yunfeng. „Infinity problems and countability problems for ω-automata“. Information Processing Letters 100, Nr. 4 (November 2006): 151–53. http://dx.doi.org/10.1016/j.ipl.2006.06.011.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

20

Kuich, Werner. „Automata and languages generalized to ω-continuous semirings“. Theoretical Computer Science 79, Nr. 1 (Februar 1991): 137–50. http://dx.doi.org/10.1016/0304-3975(91)90147-t.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

21

Touati, H. J., und R. K. Brayton. „Testing Language Containment for ω-Automata Using BDDs“. Information and Computation 118, Nr. 1 (April 1995): 101–9. http://dx.doi.org/10.1006/inco.1995.1055.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

22

SAOUDI, A., D. E. MULLER und P. E. SCHUPP. „ON THE COMPLEXITY OF RECOGNIZABLE ω-TREE SETS AND NERODE THEOREM“. International Journal of Foundations of Computer Science 01, Nr. 01 (März 1990): 11–21. http://dx.doi.org/10.1142/s0129054190000035.

Der volle Inhalt der Quelle

Annotation:

In this paper we consider the extension of Nerode theorem to infinite trees. Unfortunately, we prove that this extension is not possible. We give some characterizations of recognizable and rational ω-tree sets in terms of ω-tree automata. We consider some complexity measures of recognizable and rational ω-tree sets and prove that these measures define infinite hierarchies.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

23

KUTRIB, MARTIN, ANDREAS MALCHER und MATTHIAS WENDLANDT. „SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA“. International Journal of Foundations of Computer Science 25, Nr. 07 (November 2014): 877–96. http://dx.doi.org/10.1142/s0129054114400139.

Der volle Inhalt der Quelle

Annotation:

We investigate the descriptional complexity of deterministic one-way multi-head finite automata accepting unary languages. It is known that in this case the languages accepted are regular. Thus, we study the increase of the number of states when an n-state k-head finite automaton is simulated by a classical (one-head) deterministic or nondeterministic finite automaton. In the former case upper and lower bounds that are tight in the order of magnitude are shown. For the latter case we obtain an upper bound of O(n2k) and a lower bound of Ω(nk) states. We investigate also the costs for the conversion of one-head nondeterministic finite automata to deterministic k-head finite automata, that is, we trade nondeterminism for heads. In addition, we study how the conversion costs vary in the special case of finite and, in particular, of singleton unary lanuages. Finally, as an application of the simulation results, we show that decidability problems for unary deterministic k-head finite automata such as emptiness or equivalence are LOGSPACE-complete.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

24

Löding, Christof. „Simplification Problems for Deterministic Pushdown Automata on Infinite Words“. International Journal of Foundations of Computer Science 26, Nr. 08 (Dezember 2015): 1041–68. http://dx.doi.org/10.1142/s0129054115400122.

Der volle Inhalt der Quelle

Annotation:

The article surveys some decidability results concerning simplification problems for DPDAs on infinite words (ω-DPDAs). We summarize some recent results on the regularity problem, which asks for a given ω-DPDA, whether its language can also be accepted by a finite automaton. The results also give some insights on the equivalence problem for a subclass of ω-DPDA. Furthermore, we present some new results on the parity index problem for ω-DPDAs. For the specification of a parity condition, the states of the ω-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given ω-DPDA. We provide some decidability results on variations of this question for some classes of ω-DPDAs.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

25

SAOUDI, A. „PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS“. International Journal of Foundations of Computer Science 03, Nr. 01 (März 1992): 21–39. http://dx.doi.org/10.1142/s0129054192000048.

Der volle Inhalt der Quelle

Annotation:

We introduce various types of top-down pushdown infinite tree automata. We extend the Landweber-Staiger-Wagner hierarchy to pushdown infinite tree automata. We prove that the extension of Kleene’s theorem to pushdown infinite tree automata is not possible. We characterize recognizable (i.e. regular) infinite trees and extend Eilenberg’s theorem to ω-tree pushdown automata. We give some characterizations of infinite computations of nondeterministic context-free program schemes. We show that the equivalence problem for nondeterministic context-free program schemes is unsolvable.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

26

Droste, Manfred, Zoltán Ésik und Werner Kuich. „The Triple-Pair Construction for Weighted ω-Pushdown Automata“. Electronic Proceedings in Theoretical Computer Science 252 (21.08.2017): 101–13. http://dx.doi.org/10.4204/eptcs.252.12.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

27

La Torre, Salvatore, und Margherita Napoli. „A Model of Finite Automata on Timed ω-Trees“. Electronic Notes in Theoretical Computer Science 42 (Januar 2001): 158–73. http://dx.doi.org/10.1016/s1571-0661(04)80884-3.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

28

Bhatia, Amandeep Singh, und Ajay Kumar. „Quantum ω-Automata over Infinite Words and Their Relationships“. International Journal of Theoretical Physics 58, Nr. 3 (12.01.2019): 878–89. http://dx.doi.org/10.1007/s10773-018-3983-0.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

29

DANG, ZHE, und OSCAR H. IBARRA. „THE EXISTENCE OF ω-CHAINS FOR TRANSITIVE MIXED LINEAR RELATIONS AND ITS APPLICATIONS“. International Journal of Foundations of Computer Science 13, Nr. 06 (Dezember 2002): 911–36. http://dx.doi.org/10.1142/s0129054102001539.

Der volle Inhalt der Quelle

Annotation:

We show that it is decidable whether a transitive mixed linear relation has an ω-chain. Using this result, we study a number of liveness verification problems for generalized timed automata within a unified framework. More precisely, we prove that (1) the mixed linear liveness problem for a timed automaton with dense clocks, reversal-bounded counters, and a free counter is decidable, and (2) the Presburger liveness problem for a timed automaton with discrete clocks, reversal-bounded counters, and a pushdown stack is decidable.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

30

PETTOROSSI, ALBERTO, MAURIZIO PROIETTI und VALERIO SENNI. „Transformations of logic programs on infinite lists“. Theory and Practice of Logic Programming 10, Nr. 4-6 (Juli 2010): 383–99. http://dx.doi.org/10.1017/s1471068410000177.

Der volle Inhalt der Quelle

Annotation:

AbstractWe consider an extension of logic programs, called ω-programs, that can be used to define predicates overinfinite lists. ω-programs allow us to specify properties of the infinite behavior of reactive systems and, in general, properties of infinite sequences of events. The semantics of ω-programs is an extension of the perfect model semantics. We present variants of the familiar unfold/fold rules which can be used for transforming ω-programs. We show that these new rules are correct, that is, their application preserves the perfect model semantics. Then we outline a general methodology based on program transformation for verifying properties of ω-programs. We demonstrate the power of our transformation-based verification methodology by proving some properties of Büchi automata and ω-regular languages.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

31

DUPARC, JACQUES, und MARIANE RISS. „THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS“. International Journal of Algebra and Computation 16, Nr. 01 (Februar 2006): 161–85. http://dx.doi.org/10.1142/s0218196706002871.

Der volle Inhalt der Quelle

Annotation:

In 1997, following the works of Klaus W. Wagner on ω-regular sets, Olivier Carton and Dominique Perrin introduced the notions of chains and superchains for ω-semigroups. There is a clear correspondence between the algebraic representation of each of these operations and the automata-theoretical one. Unfortunately, chains and superchains do not suffice to describe the whole Wagner hierarchy. We introduce a third notion that completes the task undertaken by these two authors.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

32

DROSTE, MANFRED, und ULRIKE PÜSCHMANN. „ON WEIGHTED BÜCHI AUTOMATA WITH ORDER-COMPLETE WEIGHTS“. International Journal of Algebra and Computation 17, Nr. 02 (März 2007): 235–60. http://dx.doi.org/10.1142/s0218196707003585.

Der volle Inhalt der Quelle

Annotation:

We investigate Büchi automata with weights for the transitions. Assuming that the weights are taken in a suitable ordered semiring, we show how to define the behaviors of these automata on infinite words. Our main result shows that the formal power series arising in this way are precisely the ones which can be constructed using ω-rational operations. This extends the classical Kleene–Schützenberger result for weighted finite automata to the case of infinite words and generalizes Büchi's theorem on languages of infinite words. We also derive versions of our main result for non-complete semirings and for other automata models.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

33

CHUA, LEON O., und GIOVANNI E. PAZIENZA. „A NONLINEAR DYNAMICS PERSPECTIVE OF WOLFRAM'S NEW KIND OF SCIENCE PART XII: PERIOD-3, PERIOD-6, AND PERMUTIVE RULES“. International Journal of Bifurcation and Chaos 19, Nr. 12 (Dezember 2009): 3887–4038. http://dx.doi.org/10.1142/s0218127409025365.

Der volle Inhalt der Quelle

Annotation:

This 12th part of our Nonlinear Dynamics Perspective of Cellular Automata concludes a series of three articles devoted to CA local rules having robust periodic ω-limit orbits. Here, we consider only the two rules, [Formula: see text] and [Formula: see text], constituting the third of the six groups in which we classified the 1D binary Cellular Automata. Among the numerous theoretical results contained in this article, we emphasize the complete characterization of the ω-limit orbits, both robust and nonrobust, of these two rules and the proof that period-3 and period-6 ω-limit orbits are dense for [Formula: see text] and [Formula: see text], respectively. Furthermore, we will also introduce the fundamental concepts of perfect period-T orbitsets and riddled basins, and see how they emerge in rule [Formula: see text]. As stated in the title, we also focus on permutive rules, which have been introduced in a previous installment of our series but never thoroughly studied. Indeed, we will review some of the well-known properties of such rules, like the surjectivity, examining their implications for finite and bi-infinite Cellular Automata. Finally, we propose a new list of the 88 globally-independent local rules, which is slightly different from the one we have used so far but has the great advantage of being selected via a rigorous methodology and not an arbitrary choice. For the sake of completeness, we display in the appendix the basin tree diagrams and the portraits of the ω-limit orbits of the rules from this refined table which have not yet been reported in our previous articles.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

34

Esparza, Javier, Jan Křetínský und Salomon Sickert. „A Unified Translation of Linear Temporal Logic to ω-Automata“. Journal of the ACM 67, Nr. 6 (16.11.2020): 1–61. http://dx.doi.org/10.1145/3417995.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

35

Isaak, Dimitri, und Christof Löding. „Efficient inclusion testing for simple classes of unambiguous ω-automata“. Information Processing Letters 112, Nr. 14-15 (August 2012): 578–82. http://dx.doi.org/10.1016/j.ipl.2012.04.010.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

36

CHAMPARNAUD, JEAN-MARC, FRANCK GUINGNE und GEORGES HANSEL. „COVER TRANSDUCERS FOR FUNCTIONS WITH FINITE DOMAIN“. International Journal of Foundations of Computer Science 16, Nr. 05 (Oktober 2005): 851–65. http://dx.doi.org/10.1142/s0129054105003339.

Der volle Inhalt der Quelle

Annotation:

Cover automata were introduced a few years ago for designing a compact representation of finite languages. Our aim is to extend this notion to cover transducers for functions with finite domain. Given two alphabets Σ and Ω, and a function α : Σ* → Ω* of order l (the maximal length of a word in the domain of α), a cover transducer for α is any subsequential transducer that realizes the function α when its input is restricted to the set of words of Σ* having a length not greater than l. We study the problem of reducing the number of states of a cover transducer. We report experimental results, from an implementation using WFSC (Weighted Finite State Compiler), a Xerox tool for handling weighted finite state automata and transducers.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

37

Bedon, Nicolas. „Automata, Semigroups and Recognizability of Words on Ordinals“. International Journal of Algebra and Computation 08, Nr. 01 (Februar 1998): 1–21. http://dx.doi.org/10.1142/s0218196798000028.

Der volle Inhalt der Quelle

Annotation:

For a given integer n, we define ωn-semigroups as a generalization of ω-semigroups for languages of words of length less than ωn+1. When they are finite, those algebraic structures define the same sets as those recognized by Choueka automata. These sets are also equivalent to regular expressions in which an unary ω operator standing for the infinite repetition of a language is as free as the Kleene closure operator is. Naturally, the notion of syntactic congruence still works on ωn-semigroups: among all ωn-semigroups recognizing a regular language X, there exists an unique ωn-semigroup of which all others are refinements.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

38

Safra, Shmuel. „Exponential Determinization for ω‐Automata with a Strong Fairness Acceptance Condition“. SIAM Journal on Computing 36, Nr. 3 (Januar 2006): 803–14. http://dx.doi.org/10.1137/s0097539798332518.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

39

LIN, YIH-KAI, und HSU-CHUN YEN. „An ω-Automata Approach to the Compression of Bi-Level Images“. Electronic Notes in Theoretical Computer Science 31 (2000): 170–84. http://dx.doi.org/10.1016/s1571-0661(05)80338-x.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

40

Klein, Joachim, und Christel Baier. „Experiments with deterministic ω-automata for formulas of linear temporal logic“. Theoretical Computer Science 363, Nr. 2 (Oktober 2006): 182–95. http://dx.doi.org/10.1016/j.tcs.2006.07.022.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

41

Melnikov, B. F. „2 ω-finite automata and sets of obstructions of their languages“. Korean Journal of Computational & Applied Mathematics 6, Nr. 3 (September 1999): 565–74. http://dx.doi.org/10.1007/bf03009949.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

42

Giannakis, Konstantinos, Georgia Theocharopoulou, Christos Papalitsas, Theodore Andronikos und Panayiotis Vlamos. „Associating ω-automata to path queries on Webs of Linked Data“. Engineering Applications of Artificial Intelligence 51 (Mai 2016): 115–23. http://dx.doi.org/10.1016/j.engappai.2016.01.013.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

43

Tran, Nicholas. „The Book Review Column“. ACM SIGACT News 55, Nr. 1 (26.03.2024): 6–19. http://dx.doi.org/10.1145/3654780.3654782.

Der volle Inhalt der Quelle

Annotation:

I am a fan of Sheldon Ross' textbooks on probability; they are concise and full of interesting exercises. He and Erol Pek¨oz have just released a second edition of A Second Course in Probability (Cambridge University Press, 2023), which promises a rigorous but accessible and modern introduction to a selection of advanced topics in the field. Javier Esparza's work includes using automata to study model checking, program analysis and verification. His book (coauthored with Michael Blondin) Automata Theory: An Algorithmic Approach (The MIT Press, 2023) emphasizes efficient constructions of (ω-)automata and other algorithmic concerns. Filterworld: How Algorithms Flattened Culture by New Yorker staff writer Kyle Chayka (Doubleday, 2024) investigates the pervasive impact of algorithms on consumption and distribution of culture and explores ways to reclaim our freedom from the digital overlord.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

44

MALETTI, ANDREAS. „RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA“. International Journal of Foundations of Computer Science 16, Nr. 04 (August 2005): 723–41. http://dx.doi.org/10.1142/s012905410500325x.

Der volle Inhalt der Quelle

Annotation:

Bottom-up tree series transducers (tst) over the semiring [Formula: see text] are implemented with the help of bottom-up weighted tree automata (wta) over an extension of [Formula: see text]. Therefore bottom-up [Formula: see text]-weighted tree automata ([Formula: see text]-wta) with [Formula: see text] a distributive Ω-algebra are introduced. A [Formula: see text]-wta is essentially a wta but uses as transition weight an operation symbol of the Ω-algebra [Formula: see text] instead of a semiring element. The given tst is implemented with the help of a [Formula: see text]-wta, essentially showing that [Formula: see text]-wta are a joint generalization of tst (using IO-substitution) and wta. Then a semiring and a wta are constructed such that the wta computes a formal representation of the semantics of the [Formula: see text]-wta. The applicability of the obtained presentation result is demonstrated by deriving a pumping lemma for deterministic finite [Formula: see text]-wta from a known pumping lemma for deterministic finite wta. Finally, it is observed that the known decidability results for emptiness cannot be applied to obtain decidability of emptiness for finite [Formula: see text]-wta. Thus with help of a weaker version of the derived pumping lemma, decidability of the emptiness problem for finite [Formula: see text]-wta is shown under mild conditions on [Formula: see text].

APA, Harvard, Vancouver, ISO und andere Zitierweisen

45

Moriya, Tetsuo. „ω-Languages accepted by finite automata whose structures are cascade products of resets“. Information Sciences 61, Nr. 1-2 (April 1992): 179–86. http://dx.doi.org/10.1016/0020-0255(92)90039-b.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

46

Barozzini, David, David de Frutos-Escrig, Dario Della Monica, Angelo Montanari und Pietro Sala. „Beyond ω-regular languages: ωT-regular expressions and their automata and logic counterparts“. Theoretical Computer Science 813 (April 2020): 270–304. http://dx.doi.org/10.1016/j.tcs.2019.12.029.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

47

Almeida, Jorge, und Marc Zeitoun. „An automata-theoretic approach to the word problem for ω -terms over R“. Theoretical Computer Science 370, Nr. 1-3 (Februar 2007): 131–69. http://dx.doi.org/10.1016/j.tcs.2006.10.019.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

48

Fleischer, Lukas, und Manfred Kufleitner. „The complexity of weakly recognizing morphisms“. RAIRO - Theoretical Informatics and Applications 53, Nr. 1-2 (15.11.2018): 1–17. http://dx.doi.org/10.1051/ita/2018006.

Der volle Inhalt der Quelle

Annotation:

Weakly recognizing morphisms from free semigroups onto finite semigroups are a classical way for defining the class of ω-regular languages, i.e., a set of infinite words is weakly recognizable by such a morphism if and only if it is accepted by some Büchi automaton. We study the descriptional complexity of various constructions and the computational complexity of various decision problems for weakly recognizing morphisms. The constructions we consider are the conversion from and to Büchi automata, the conversion into strongly recognizing morphisms, as well as complementation. We also show that the fixed membership problem is NC1-complete, the general membership problem is in L and that the inclusion, equivalence and universality problems are NL-complete. The emptiness problem is shown to be NL-complete if the input is given as a non-surjective morphism.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

49

Barua, Rana. „The Hausdorff-Kuratowski hierarchy of ω-regular languages and a hierarchy of Muller automata“. Theoretical Computer Science 96, Nr. 2 (April 1992): 345–60. http://dx.doi.org/10.1016/0304-3975(92)90342-d.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

50

INOUE, KATSUSHI, ITSUO SAKURAMOTO, MAKOTO SAKAMOTO und ITSUO TAKANAMI. „TWO TOPICS CONCERNING TWO-DIMENSIONAL AUTOMATA OPERATING IN PARALLEL“. International Journal of Pattern Recognition and Artificial Intelligence 06, Nr. 02n03 (August 1992): 211–25. http://dx.doi.org/10.1142/s0218001492000126.

Der volle Inhalt der Quelle

Annotation:

This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimensional alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular acceptors (NUPCAs), and show that Ω ( diameter × log diameter ) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimensional alternating Turing machines (2-ATMs) operating in small space, and show that if L (n) is a two-dimensionally space-constructible function such that lim n → ∞ L (n)/ loglog n > 1 and L (n) ≤ log n, and L′ (n) is a function satisfying L′ (n) =o (L(n)), then there exists a set accepted by some strongly L (n) space-bounded two-dimensional deterministic Turing machine, but not accepted by any weakly L′ (n) space-bounded 2-ATM, and thus there exists a rich space hierarchy for weakly S (n) space-bounded 2-ATMs with loglog n ≤ S (n) ≤ log n.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!