Einloggen

Thematische Bibliographien / Omega-Regular languages

Inhaltsverzeichnis

Zeitschriftenartikel
Bücher
Buchteile
Konferenzberichte

Auswahl der wissenschaftlichen Literatur zum Thema „Omega-Regular languages“

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 den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "Omega-Regular languages" 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.

Zeitschriftenartikel zum Thema "Omega-Regular languages"

1

Angluin, Dana, und Dana Fisman. „Learning regular omega languages“. Theoretical Computer Science 650 (Oktober 2016): 57–72. http://dx.doi.org/10.1016/j.tcs.2016.07.031.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Angluin, Dana, und Dana Fisman. „Regular omega-Languages with an Informative Right Congruence“. Electronic Proceedings in Theoretical Computer Science 277 (07.09.2018): 265–79. http://dx.doi.org/10.4204/eptcs.277.19.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Falah, Amin, Shibashis Guha und Ashutosh Trivedi. „Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP“. Proceedings of the International Conference on Automated Planning and Scheduling 33, Nr. 1 (01.07.2023): 578–86. http://dx.doi.org/10.1609/icaps.v33i1.27239.

Der volle Inhalt der Quelle

Annotation:

Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time and stochastic environments. When the stochastic evolution of the environment is only available via sampling, model-free reinforcement learning (RL) is the algorithm-of-choice to compute optimal decision sequence. RL, on the other hand, requires the learning objective to be encoded as scalar reward signals. Since doing such translations manually is both tedious and error-prone, a number of techniques have been proposed to translate high-level objectives (expressed in logic or automata formalism) to scalar rewards for discrete-time Markov decision processes. Unfortunately, no automatic translation exists for CTMDPs. We consider CTMDP environments against the learning objectives expressed as omega-regular languages. Omega-regular languages generalize regular languages to infinite-horizon specifications and can express properties given in popular linear-time logic LTL. To accommodate the dense-time nature of CTMDPs, we consider two different semantics of omega-regular objectives: 1) satisfaction semantics where the goal of the learner is to maximize the probability of spending positive time in the good states, and 2) expectation semantics where the goal of the learner is to optimize the long-run expected average time spent in the ''good states'' of the automaton. We present an approach enabling correct translation to scalar reward signals that can be readily used by off-the-shelf RL algorithms for CTMDPs. We demonstrate the effectiveness of the proposed algorithms by evaluating it on some popular CTMDP benchmarks with omega-regular objectives.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Almeida, J., J. C. Costa und M. Zeitoun. „McCammond’s normal forms for free aperiodic semigroups revisited“. LMS Journal of Computation and Mathematics 18, Nr. 1 (2015): 130–47. http://dx.doi.org/10.1112/s1461157014000448.

Der volle Inhalt der Quelle

Annotation:

AbstractThis paper revisits the solution of the word problem for ${\it\omega}$-terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCammond’s algorithm, based on normal forms for such terms, uses McCammond’s solution of the word problem for certain Burnside semigroups. In this paper, we establish a new, simpler, correctness proof of McCammond’s algorithm, based on properties of certain regular languages associated with the normal forms. This method leads to new applications.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Gnatenko, Anton Romanovich, und Vladimir Anatolyevich Zakharov. „On the Model Checking Problem for Some Extension of CTL*“. Modeling and Analysis of Information Systems 27, Nr. 4 (20.12.2020): 428–41. http://dx.doi.org/10.18255/1818-1015-2020-4-428-441.

Der volle Inhalt der Quelle

Annotation:

Sequential reactive systems include programs and devices that work with two streams of data and convert input streams of data into output streams. Such information processing systems include controllers, device drivers, computer interpreters. The result of the operation of such computing systems are infinite sequences of pairs of events of the request-response type, and, therefore, finite transducers are most often used as formal models for them. The behavior of transducers is represented by binary relations on infinite sequences, and so, traditional applied temporal logics (like HML, LTL, CTL, mu-calculus) are poorly suited as specification languages, since omega-languages, not binary relations on omega-words are used for interpretation of their formulae. To provide temporal logics with the ability to define properties of transformations that characterize the behavior ofreactive systems, we introduced new extensions ofthese logics, which have two distinctive features: 1) temporal operators are parameterized, and languages in the input alphabet oftransducers are used as parameters; 2) languages in the output alphabet oftransducers are used as basic predicates. Previously, we studied the expressive power ofnew extensions Reg-LTL and Reg-CTL ofthe well-known temporal logics oflinear and branching time LTL and CTL, in which it was allowed to use only regular languages for parameterization of temporal operators and basic predicates. We discovered that such a parameterization increases the expressive capabilities oftemporal logic, but preserves the decidability of the model checking problem. For the logics mentioned above, we have developed algorithms for the verification of finite transducers. At the next stage of our research on the new extensions of temporal logic designed for the specification and verification of sequential reactive systems, we studied the verification problem for these systems using the temporal logic Reg-CTL*, which is an extension ofthe Generalized Computational Tree Logics CTL*. In this paper we present an algorithm for checking the satisfiability of Reg-CTL* formulae on models of finite state transducers and show that this problem belongs to the complexity class ExpSpace.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

CURRIE, JAMES D., NARAD RAMPERSAD und KALLE SAARI. „Suffix conjugates for a class of morphic subshifts“. Ergodic Theory and Dynamical Systems 35, Nr. 6 (04.06.2014): 1767–82. http://dx.doi.org/10.1017/etds.2014.5.

Der volle Inhalt der Quelle

Annotation:

Let $A$ be a finite alphabet and $f:~A^{\ast }\rightarrow A^{\ast }$ be a morphism with an iterative fixed point $f^{{\it\omega}}({\it\alpha})$, where ${\it\alpha}\in A$. Consider the subshift $({\mathcal{X}},T)$, where ${\mathcal{X}}$ is the shift orbit closure of $f^{{\it\omega}}({\it\alpha})$ and $T:~{\mathcal{X}}\rightarrow {\mathcal{X}}$ is the shift map. Let $S$ be a finite alphabet that is in bijective correspondence via a mapping $c$ with the set of non-empty suffixes of the images $f(a)$ for $a\in A$. Let ${\mathcal{S}}\subset S^{\mathbb{N}}$ be the set of infinite words $\mathbf{s}=(s_{n})_{n\geq 0}$ such that ${\it\pi}(\mathbf{s}):=c(s_{0})f(c(s_{1}))f^{2}(c(s_{2}))\cdots \in {\mathcal{X}}$. We show that if $f$ is primitive, $f^{{\it\omega}}({\it\alpha})$ is aperiodic, and $f(A)$ is a suffix code, then there exists a mapping $H:~{\mathcal{S}}\rightarrow {\mathcal{S}}$ such that $({\mathcal{S}},H)$ is a topological dynamical system and ${\it\pi}:~({\mathcal{S}},H)\rightarrow ({\mathcal{X}},T)$ is a conjugacy; we call $({\mathcal{S}},H)$ the suffix conjugate of $({\mathcal{X}},T)$. In the special case where $f$ is the Fibonacci or Thue–Morse morphism, we show that the subshift $({\mathcal{S}},T)$ is sofic, that is, the language of ${\mathcal{S}}$ is regular.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

Huy, Phan Trung, und Nguyễn Quý Khang. „Regular omega-languages and finite monoids having infinite products.“ Journal of Computer Science and Cybernetics 19, Nr. 2 (26.07.2012). http://dx.doi.org/10.15625/1813-9663/19/2/1512.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

Rabinovich, Alexander, und Doron Tiferet. „Ambiguity Hierarchy of Regular Infinite Tree Languages“. Logical Methods in Computer Science Volume 17, Issue 3 (13.08.2021). http://dx.doi.org/10.46298/lmcs-17(3:18)2021.

Der volle Inhalt der Quelle

Annotation:

An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting computations. An automaton is boundedly ambiguous if it is k-ambiguous for some $k \in \mathbb{N}$. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. The degree of ambiguity of a regular language is defined in a natural way. A language is k-ambiguous (respectively, boundedly, finitely, countably ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly, finitely, countably ambiguous) automaton. Over finite words every regular language is accepted by a deterministic automaton. Over finite trees every regular language is accepted by an unambiguous automaton. Over $\omega$-words every regular language is accepted by an unambiguous B\"uchi automaton and by a deterministic parity automaton. Over infinite trees Carayol et al. showed that there are ambiguous languages. We show that over infinite trees there is a hierarchy of degrees of ambiguity: For every k > 1 there are k-ambiguous languages that are not k - 1 ambiguous; and there are finitely (respectively countably, uncountably) ambiguous languages that are not boundedly (respectively finitely, countably) ambiguous.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

9

Klarlund, Nils, Madhavan Mukund und Milind Sohoni. „Determinizing Asynchronous Automata on Infinite Inputs“. BRICS Report Series 2, Nr. 58 (28.11.1995). http://dx.doi.org/10.7146/brics.v2i58.19959.

Der volle Inhalt der Quelle

Annotation:

Asynchronous automata are a natural distributed machine model<br />for recognizing trace languages - languages defined over an alphabet<br />equipped with an independence relation.<br />To handle infinite traces, Gastin and Petit introduced Buchi asynchronous<br />automata, which accept precisely the class of omega-regular trace<br />languages. Like their sequential counterparts, these automata need to<br />be non-deterministic in order to capture all omega-regular languages. Thus<br />complementation of these automata is non-trivial. Complementation<br />is an important operation because it is fundamental for treating the<br />logical connective "not" in decision procedures for monadic second-order<br />logics. Subsequently, Diekert and Muscholl solved the complementation<br />problem by showing that with a Muller acceptance condition, deterministic<br />automata suffice for recognizing omega-regular trace languages.<br />However, a direct determinization procedure, extending the classical<br />subset construction, has proved elusive.<br />In this paper, we present a direct determinization procedure for<br />Buchi asynchronous automata, which generalizes Safra's construction<br />for sequential Buchi automata. As in the sequential case, the blow-up<br />in the state space is essentially that of the underlying subset construction.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

Bartholdi, Laurent, und Marialaura Noce. „Tree languages and branched groups“. Mathematische Zeitschrift 303, Nr. 4 (20.03.2023). http://dx.doi.org/10.1007/s00209-023-03249-y.

Der volle Inhalt der Quelle

Annotation:

AbstractWe study the portraits of isometries of rooted trees—the labelling of the tree, at each vertex, by the permutation of its descendants—in terms of languages. We characterize regularly branched self-similar groups in terms of $$\omega $$ ω -regular languages. We deduce the algorithmic decidability of some problems, such as the comparison of regularly branched contracting groups, and their orbit structure on the boundary of the rooted tree.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Mehr Quellen

Bücher zum Thema "Omega-Regular languages"

1

Greek Exercise Book: The Noun and the Regular Verb In -[Omega. Creative Media Partners, LLC, 2022.

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Greek Exercise Book: The Noun and the Regular Verb In -[Omega. Creative Media Partners, LLC, 2018.

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Greek Exercise Book: The Noun and the Regular Verb In -[Omega. Creative Media Partners, LLC, 2022.

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Kaegi, Adolf, Henri Ternaux-Compans und James Aloysius Kleist. Greek Exercise Book: The Noun and the Regular Verb in -[omega. Franklin Classics Trade Press, 2018.

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Kaegi, Adolf, Henri Ternaux-Compans und James Aloysius Kleist. Greek Exercise Book: The Noun and the Regular Verb In -[Omega. Creative Media Partners, LLC, 2018.

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Buchteile zum Thema "Omega-Regular languages"

1

Angluin, Dana, und Dana Fisman. „Learning Regular Omega Languages“. In Lecture Notes in Computer Science, 125–39. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-11662-4_10.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Edixhoven, Luc, und Sung-Shik Jongmans. „Balanced-By-Construction Regular and $$\omega $$-Regular Languages“. In Developments in Language Theory, 130–42. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81508-0_11.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Dimitrova, Rayna, Bernd Finkbeiner und Hazem Torfah. „Approximate Automata for Omega-Regular Languages“. In Automated Technology for Verification and Analysis, 334–49. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-31784-3_19.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Chen, Zhe, Yunyun Chen, Robert M. Hierons und Yifan Wu. „Four-Valued Monitorability of $$\omega $$-Regular Languages“. In Formal Methods and Software Engineering, 198–214. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-63406-3_12.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Orekhovskii, Vladislav, und Victor Selivanov. „Logic vs Topology on Regular $$\omega $$-languages“. In Lecture Notes in Computer Science, 141–53. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-36978-0_12.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

Skrzypczak, Michał. „Separation for $$\omega \mathrm {B}$$ - and $$\omega \mathrm {S}$$ -regular Languages“. In Descriptive Set Theoretic Methods in Automata Theory, 183–203. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. http://dx.doi.org/10.1007/978-3-662-52947-8_11.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

Michaud, Thibaud, und Alexandre Duret-Lutz. „Practical Stutter-Invariance Checks for $$\omega $$ -Regular Languages“. In Model Checking Software, 84–101. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-23404-5_7.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

Winkler, Tobias, Christina Gehnen und Joost-Pieter Katoen. „Model Checking Temporal Properties of Recursive Probabilistic Programs“. In Lecture Notes in Computer Science, 449–69. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99253-8_23.

Der volle Inhalt der Quelle

Annotation:

AbstractProbabilistic pushdown automata (pPDA) are a standard operational model for programming languages involving discrete random choices, procedures, and returns. Temporal properties are useful for gaining insight into the chronological order of events during program execution. Existing approaches in the literature have focused mostly on $$\omega $$ ω -regular and LTL properties. In this paper, we study the model checking problem of pPDA against $$\omega $$ ω -visibly pushdown languages that can be described by specification logics such as CaRet and are strictly more expressive than $$\omega $$ ω -regular properties. With these logical formulae, it is possible to specify properties that explicitly take the structured computations arising from procedural programs into account. For example, CaRet is able to match procedure calls with their corresponding future returns, and thus allows to express fundamental program properties like total and partial correctness.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

9

Löding, Christof, und Anton Pirogov. „Ambiguity, Weakness, and Regularity in Probabilistic Büchi Automata“. In Lecture Notes in Computer Science, 522–41. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-45231-5_27.

Der volle Inhalt der Quelle

Annotation:

AbstractProbabilistic Büchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this work we extend the known classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical $$\omega $$ ω -automata. Furthermore, we investigate the expressivity of the not yet considered but natural class of weak PBA, and we also show that the regularity problem for weak PBA is undecidable.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

Li, Yong, Sven Schewe und Qiyi Tang. „A Novel Family of Finite Automata for Recognizing and Learning $$\omega $$-Regular Languages“. In Automated Technology for Verification and Analysis, 53–73. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-45329-8_3.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Konferenzberichte zum Thema "Omega-Regular languages"

1

Chen, Jianhui, und Fei He. „Proving almost-sure termination by omega-regular decomposition“. In PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3385412.3386002.

Der volle Inhalt der Quelle

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!