Log in

Relevant bibliographies by topics / Omega-Regular languages / Journal articles

To see the other types of publications on this topic, follow the link: Omega-Regular languages.

Journal articles 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 top 25 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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\&quot;{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

11

Angluin, Dana, and Dana Fisman. "Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages." Logical Methods in Computer Science Volume 20, Issue 4 (November 8, 2024). http://dx.doi.org/10.46298/lmcs-20(4:10)2024.

Full text

Abstract:

A characteristic sample for a language $L$ and a learning algorithm $\textbf{L}$ is a finite sample of words $T_L$ labeled by their membership in $L$ such that for any sample $T \supseteq T_L$ consistent with $L$, on input $T$ the learning algorithm $\textbf{L}$ returns a hypothesis equivalent to $L$. Which omega automata have characteristic sets of polynomial size, and can these sets be constructed in polynomial time? We address these questions here. In brief, non-deterministic omega automata of any of the common types, in particular B\"uchi, do not have characteristic samples of polynomial s

APA, Harvard, Vancouver, ISO, and other styles

12

Klarlund, Nils, Madhavan Mukund, and Milind Sohoni. "Determinizing Asynchronous Automata on Infinite Inputs." BRICS Report Series 2, no. 58 (1995). http://dx.doi.org/10.7146/brics.v2i58.19959.

Full text

Abstract:

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&l

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Bojańczyk, Mikołaj, and Bartek Klin. "A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra." Logical Methods in Computer Science Volume 15, Issue 4 (November 29, 2019). https://doi.org/10.23638/lmcs-15(4:11)2019.

Full text

Abstract:

$\omega$-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as $\omega$-semigroups are convenient algebras for infinite words. In the algebraic theory of languages, one hopes that a language is regular if and only if it is recognized by an algebra that is finite in some simple sense. We show that, for infinite trees, the situation is not so simple: there exists an $\omega$-clone that is finite on every sort and finitely generated, but recognizes a non-regular language.

APA, Harvard, Vancouver, ISO, and other styles

15

Bohn, León, and Christof Löding. "Constructing Deterministic Parity Automata from Positive and Negative Examples." TheoretiCS Volume 3 (July 30, 2024). http://dx.doi.org/10.46298/theoretics.24.17.

Full text

Abstract:

We present a polynomial time algorithm that constructs a deterministic parity automaton (DPA) from a given set of positive and negative ultimately periodic example words. We show that this algorithm is complete for the class of $\omega$-regular languages, that is, it can learn a DPA for each regular $\omega$-language. For use in the algorithm, we give a definition of a DPA, that we call the precise DPA of a language, and show that it can be constructed from the syntactic family of right congruences for that language (introduced by Maler and Staiger in 1997). Depending on the structure of the l

APA, Harvard, Vancouver, ISO, and other styles

16

Bartholdi, Laurent, and Marialaura Noce. "Tree languages and branched groups." Mathematische Zeitschrift 303, no. 4 (2023). http://dx.doi.org/10.1007/s00209-023-03249-y.

Full text

Abstract:

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, and other styles

17

Jagtap, Pushpak, and Dimos V. Dimarogonas. "Controller synthesis against omega‐regular specifications: A funnel‐based control approach." International Journal of Robust and Nonlinear Control, March 25, 2024. http://dx.doi.org/10.1002/rnc.7339.

Full text

Abstract:

AbstractThe paper focuses on the problem of formal synthesis of controllers for control‐affine nonlinear systems against complex properties. Our goal is to design a closed‐form control policy that guarantees the satisfaction of complex properties that are expressed using ()‐regular languages and equivalently recognized by nondeterministic Büchi automata (NBA). We propose leveraging a funnel‐based control approach to provide a closed‐form solution to the problem. Our approach decomposes the specification represented by NBA into a sequence of reachability problems, which we solve using a funnel‐

APA, Harvard, Vancouver, ISO, and other styles

18

Winkler, Tobias, Christina Gehnen, and Joost-Pieter Katoen. "Model Checking Temporal Properties of Recursive Probabilistic Programs." Logical Methods in Computer Science Volume 19, Issue 4 (December 15, 2023). http://dx.doi.org/10.46298/lmcs-19(4:24)2023.

Full text

Abstract:

Probabilistic pushdown automata (pPDA) are a standard operational model for programming languages involving discrete random choices and recursive procedures. Temporal properties are useful for specifying the chronological order of events during program execution. Existing approaches for model checking pPDA against temporal properties have focused mostly on $\omega$-regular and LTL properties. In this paper, we give decidability and complexity results for the model checking problem of pPDA against $\omega$-visibly pushdown languages that can be described by specification logics such as CaRet. T

APA, Harvard, Vancouver, ISO, and other styles

19

Bojańczyk, Mikołaj, Filippo Cavallari, Thomas Place, and Michał Skrzypczak. "Regular tree languages in low levels of the Wadge Hierarchy." Logical Methods in Computer Science Volume 15, Issue 3 (September 4, 2019). https://doi.org/10.23638/lmcs-15(3:27)2019.

Full text

Abstract:

In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets $BC(\Sigma_1^0)$ (i.e. the union of the first $\omega$ levels); and for the Borel class $\Delta_2^0$ (i.e. for the union of the first $\omega_1$ levels).

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

21

Gnatenko, Anton Romanovich, and Vladimir Anatolyevoch Zakharov. "USING AN EXTENSIONS OF CTL* FOR SPECIFICATION AND VERIFICATION OF SEQUENTIAL REACTIVE SYSTEMS." System Informatics, no. 17 (2020). http://dx.doi.org/10.31144/si.2307-6410.2020.n17.p21-32.

Full text

Abstract:

Sequential reactive systems such as controllers, device drivers, computer interpreters operate with two data streams and transform input streams of data (control signals, instructions) into output streams of control signals (instructions, data). Finite state transducers are widely used as an adequate formal model for information processing systems of this kind. Since runs of transducers develop over time, temporal logics, obviously, could be used as both simple and expressive formalism for specifying the behavior of sequential reactive systems. However, the conventional applied temporal logics

APA, Harvard, Vancouver, ISO, and other styles

22

Cimatti, Alessandro, Luca Geatti, Nicola Gigante, Angelo Montanari, and Stefano Tonetta. "A first-order logic characterization of safety and co-safety languages." Logical Methods in Computer Science Volume 19, Issue 3 (August 10, 2023). http://dx.doi.org/10.46298/lmcs-19(3:13)2023.

Full text

Abstract:

Linear Temporal Logic (LTL) is one of the most popular temporal logics, that comes into play in a variety of branches of computer science. Among the various reasons of its widespread use there are its strong foundational properties: LTL is equivalent to counter-free omega-automata, to star-free omega-regular expressions, and (by Kamp's theorem) to the First-Order Theory of Linear Orders (FO-TLO). Safety and co-safety languages, where a finite prefix suffices to establish whether a word does not belong or belongs to the language, respectively, play a crucial role in lowering the complexity of p

APA, Harvard, Vancouver, ISO, and other styles

23

Dave, V., E. Filiot, S. Krishna, and N. Lhote. "Synthesis of Computable Regular Functions of Infinite Words." Logical Methods in Computer Science Volume 18, Issue 2 (June 29, 2022). http://dx.doi.org/10.46298/lmcs-18(2:23)2022.

Full text

Abstract:

Regular functions from infinite words to infinite words can be equivalently specified by MSO-transducers, streaming $\omega$-string transducers as well as deterministic two-way transducers with look-ahead. In their one-way restriction, the latter transducers define the class of rational functions. Even though regular functions are robustly characterised by several finite-state devices, even the subclass of rational functions may contain functions which are not computable (by a Turing machine with infinite input). This paper proposes a decision procedure for the following synthesis problem: giv

APA, Harvard, Vancouver, ISO, and other styles

24

-, SHWETA ARORA. "Enhancing Brain Elasticity: Key Lifestyle Habits to Unlock Genius Potential at Any Age." International Journal For Multidisciplinary Research 6, no. 4 (2024). http://dx.doi.org/10.36948/ijfmr.2024.v06i04.24367.

Full text

Abstract:

The brain is a masterpiece, often referred to as the king organ, as it governs the entire body. When the brain ceases to function, it marks the end of an individual's vitality, essentially rendering them a "vegetable." This profound importance raises a crucial question: Are we adequately nurturing and caring for our brains? In today's fast-paced world, humans often subject their brains to relentless stress and negative impulses, leading to cognitive decline. However, enhancing brain elasticity can be remarkably simple by adopting specific daily habits. These habits not only pamper the brain bu

APA, Harvard, Vancouver, ISO, and other styles

25

Paviot-Adet, Emmanuel, Denis Poitrenaud, Etienne Renault, and Yann Thierry-Mieg. "Structural Reductions and Stutter Sensitive Properties." Logical Methods in Computer Science Volume 21, Issue 2 (May 20, 2025). https://doi.org/10.46298/lmcs-21(2:15)2025.

Full text

Abstract:

Verification of properties expressed as $\omega$-regular languages such as LTL can benefit hugely from stutter insensitivity, using a diverse set of reduction strategies. However properties that are not stutter invariant, for instance due to the use of the neXt operator of LTL or to some form of counting in the logic, are not covered by these techniques in general. We propose in this paper to study a weaker property than stutter insensitivity. In a stutter insensitive language both adding and removing stutter to a word does not change its acceptance, any stuttering can be abstracted away; by d

APA, Harvard, Vancouver, ISO, and other styles

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!