Relevant bibliographies by topics / Omega-Regular languages

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'Omega-Regular languages'

Author: Grafiati
Published: 25 May 2024
Last updated: 31 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Omega-Regular languages.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Omega-Regular languages"

1

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Angluin, Dana, and Dana Fisman. "Regular omega-Languages with an Informative Right Congruence." Electronic Proceedings in Theoretical Computer Science 277 (September 7, 2018): 265–79. http://dx.doi.org/10.4204/eptcs.277.19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
Abstract:
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 l
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
Abstract:
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, and other styles
5

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

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
6

Veanes, Margus, Thomas Ball, Gabriel Ebner, and Ekaterina Zhuchko. "Symbolic Automata: Omega-Regularity Modulo Theories." Proceedings of the ACM on Programming Languages 9, POPL (2025): 33–66. https://doi.org/10.1145/3704838.

Full text
Abstract:
Symbolic automata are finite state automata that support potentially infinite alphabets, such as the set of rational numbers, generally applied to regular expressions and languages over finite words. In symbolic automata (or automata modulo A ), an alphabet is represented by an effective Boolean algebra A , supported by a decision procedure for satisfiability. Regular languages over infinite words (so called ω-regular languages) have a rich history paralleling that of regular languages over finite words, with well-known applications to model checking via Büchi automata and temporal logics. We
APA, Harvard, Vancouver, ISO, and other styles
7

Angluin, Dana, Timos Antonopoulos, and Dana Fisman. "Query learning of derived $\omega$-tree languages in polynomial time." Logical Methods in Computer Science Volume 15, Issue 3 (August 27, 2019). https://doi.org/10.23638/lmcs-15(3:21)2019.

Full text
Abstract:
We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to learn classes of $\omega$-tree languages derived from weak regular $\omega$-word languages in polynomial time. The method is a general polynomial time reduction of learning a class of derived $\omega$-tree languages to learning the underlying class of $\omega$-word languages, for any class of $\omega$-word languages recognized by a deterministic B\"{u}chi acceptor. Our reduction, combined with the polynomial t
APA, Harvard, Vancouver, ISO, and other styles
8

Esik, Zoltan, and Dexter Kozen. "On Free $\omega$-Continuous and Regular Ordered Algebras." Logical Methods in Computer Science Volume 15, Issue 4 (October 29, 2019). https://doi.org/10.23638/lmcs-15(4:4)2019.

Full text
Abstract:
We study varieties of certain ordered $\Sigma$-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we show that if $E$ is a set of inequalities between finite $\Sigma$-terms, and if $\mathcal{V}_\omega$ and $\mathcal{V}_\mathrm{reg}$ denote the varieties of all $\omega$-continuous ordered $\Sigma$-algebras and regular ordered $\Sigma$-algebras satisfying $E$, respectively, then the free $\mathcal{V}_\
APA, Harvard, Vancouver, ISO, and other styles
9

Bojańczyk, Mikołaj, and Thomas Colcombet. "Boundedness in languages of infinite words." Logical Methods in Computer Science Volume 13, Issue 4 (October 26, 2017). https://doi.org/10.23638/lmcs-13(4:3)2017.

Full text
Abstract:
We define a new class of languages of $\omega$-words, strictly extending $\omega$-regular languages. One way to present this new class is by a type of regular expressions. The new expressions are an extension of $\omega$-regular expressions where two new variants of the Kleene star $L^*$ are added: $L^B$ and $L^S$. These new exponents are used to say that parts of the input word have bounded size, and that parts of the input can have arbitrarily large sizes, respectively. For instance, the expression $(a^Bb)^\omega$ represents the language of infinite words over the letters $a,b$ where there i
APA, Harvard, Vancouver, ISO, and other styles
10

Angluin, Dana, Udi Boker, and Dana Fisman. "Families of DFAs as Acceptors of $\omega$-Regular Languages." Logical Methods in Computer Science Volume 14, Issue 1 (February 14, 2018). https://doi.org/10.23638/lmcs-14(1:15)2018.

Full text
Abstract:
Families of DFAs (FDFAs) provide an alternative formalism for recognizing $\omega$-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that $\omega$-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular la
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Omega-Regular languages"

1

Vandenhove, Pierre. "Strategy complexity of zero-sum games on graphs." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG029.

Full text
Abstract:
Les jeux sur graphes à deux joueurs et à somme nulle constituent un modèle central en informatique théorique. De tels jeux modélisent une interaction potentiellement infinie entre un système dit réactif et son environnement. Le système est considéré comme un joueur et souhaite garantir une spécification (traduite en un objectif de jeu). Son environnement est considéré comme un joueur antagoniste. Le but est de synthétiser automatiquement un contrôleur pour le système qui garantit la spécification peu importe le comportement de l'environnement, ce qui correspond à construire une stratégie gagna
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Omega-Regular languages"

1

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Omega-Regular languages"

1

Angluin, Dana, and Dana Fisman. "Learning Regular Omega Languages." In Lecture Notes in Computer Science. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-11662-4_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Das, Anupam, and Abhishek De. "A Proof Theory of ($$\omega $$-)Context-Free Languages, via Non-wellfounded Proofs." In Automated Reasoning. Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-63501-4_13.

Full text
Abstract:
AbstractWe investigate the proof theory of regular expressions with fixed points, construed as a notation for ($$\omega $$ ω -)context-free grammars. Starting with a hypersequential system for regular expressions due to Das and Pous [15], we define its extension by least fixed points and prove the soundness and completeness of its non-wellfounded proofs for the standard language model. From here we apply proof-theoretic techniques to recover an infinitary axiomatisation of the resulting equational theory, complete for inclusions of context-free languages. Finally, we extend our syntax by great
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
Abstract:
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 $$\omeg
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
Abstract:
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 p
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Omega-Regular languages"

1

Li, Yong, Sven Schewe, and Qiyi Tang. "Angluin-Style Learning of Deterministic Büchi and Co-Büchi Automata." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/498.

Full text
Abstract:
While recently developed Angluin-style learning algorithms for omega-automata have much in common with her classic DFA learning algorithm, there is a huge difference in the cost of the equivalence queries about the target automata. For omega-regular languages, the target is to learn nondeterministic Buchi automata (NBAs) through the vehicle of Families of DFAs (FDFAs). While the cost of equivalence queries is usually idealised as constant in learning, it makes a practical difference that the language equivalence checking about the learned NBAs is computationally hard. We develop efficient tech
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Omega-Regular languages' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography