Classifying regular events in symbolic logic

DOI10.1016/0022-0000(82)90016-2zbMath0503.68055OpenAlexW2013085432MaRDI QIDQ1173413

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90016-2

zbMATH Keywords

regular languages dot-depth hierarchy monadic second-order definability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ How many times do you need to go back to the future in unary temporal logic? ⋮ A Trichotomy for Regular Trail Queries ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Level Two of the Quantifier Alternation Hierarchy over Infinite Words ⋮ On dot-depth two ⋮ A graphic language based on timing diagrams ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Modulo-counting quantifiers over finite trees ⋮ Refuting learning revisited. ⋮ Characterizations of some classes of regular events ⋮ Polynomial closure of group languages and open sets of the Hall topology ⋮ First-order logic and star-free sets ⋮ A logical approach to locality in pictures languages ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ On Decidability of Intermediate Levels of Concatenation Hierarchies ⋮ First-order properties of trees, star-free expressions, and aperiodicity ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Level two of the quantifier alternation hierarchy over infinite words ⋮ Brzozowski hierarchy of $\omega$-languages ⋮ Polynomial closure of group languages and open sets of the Hall topology ⋮ First-order queries on databases embedded in an infinite structure ⋮ Polynomial closure and unambiguous product ⋮ On FO 2 Quantifier Alternation over Words ⋮ Arity and alternation: a proper hierarchy in higher order logics ⋮ On uniformity within $NC^ 1$ ⋮ Locally trivial categories and unambiguous concatenation ⋮ Polynomial closure and unambiguous product ⋮ Semigroups and languages of dot-depth two ⋮ Rational, recognizable, and aperiodic partially lossy queue languages ⋮ Permutation rewriting and algorithmic verification ⋮ Concatenation hierarchies: new bottle, old wine ⋮ Inclusion relations between some congruences related to the dot-depth hierarchy ⋮ Arity and alternation in second-order logic ⋮ Inverse monoids of dot-depth two ⋮ The half-levels of the $\mathrm {FO}_2$ alternation hierarchy ⋮ Extensions of an idea of McNaughton ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Logical definability of some rational trace languages ⋮ PARTIALLY ORDERED TWO-WAY BÜCHI AUTOMATA ⋮ Reducing the local alphabet size in tiling systems by means of 2D comma-free codes ⋮ Unnamed Item ⋮ Efficiency of automata in semi-commutation verification techniques ⋮ Aural pattern recognition experiments and the subregular hierarchy ⋮ Unnamed Item ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Conservative groupoids recognize only regular languages ⋮ The product of rational languages ⋮ Languages and scanners ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Separating Without Any Ambiguity. ⋮ Homomorphic characterization of tree languages based on comma-free encoding ⋮ Polynomial operations and hierarchies of concatenation ⋮ The expressivity of autosegmental grammars ⋮ Monadic partition logics and finite automata ⋮ On the acceptance power of regular languages ⋮ LANGUAGES VERSUS ω-LANGUAGES IN REGULAR INFINITE GAMES ⋮ A note on the number of monadic quantifiers in monadic $\Sigma ^{1}_{1}$ ⋮ Regular languages in $NC$ ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Formulas, regular languages and Boolean circuits ⋮ Reversible Regular Languages: Logical and Algebraic Characterisations ⋮ The $\omega$-inequality problem for concatenation hierarchies of star-free languages ⋮ Theme and Variations on the Concatenation Product ⋮ On a conjecture concerning dot-depth two languages ⋮ Games, equations and dot-depth two monoids ⋮ Equations and dot-depth one ⋮ Languages of dot-depth 3/2 ⋮ Pebble Weighted Automata and Weighted Logics ⋮ Some results on the dot-depth hierarchy ⋮ Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT ⋮ Fragments of first-order logic over infinite words ⋮ EQUATIONAL DESCRIPTIONS OF LANGUAGES ⋮ AROUND DOT-DEPTH ONE ⋮ A note on partially ordered tree automata ⋮ On Shuffle Ideals ⋮ Expressive power of existential first-order sentences of Büchi's sequential calculus ⋮ An application of the Ehrenfeucht-Fraisse game in formal language theory ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games ⋮ 1999 European Summer Meeting of the Association for Symbolic Logic ⋮ Partially Ordered Two-Way Büchi Automata ⋮ Separating regular languages with two quantifier alternations ⋮ Classifying regular languages by a split game ⋮ Trees, congruences and varieties of finite semigroups ⋮ Logic, semigroups and automata on words ⋮ On Existentially First-Order Definable Languages and Their Relation to NP ⋮ On All Things Star-Free ⋮ Generic results for concatenation hierarchies ⋮ Games, equations and the dot-depth hierarchy ⋮ Weighted automata ⋮ Varieties ⋮ Star free expressions over the reals ⋮ On distinguishing sets of structures by first-order sentences of minimal quantifier rank ⋮ Unnamed Item ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ A reducibility for the dot-depth hierarchy ⋮ Characterizing level one in group-based concatenation hierarchies ⋮ Algebraic tools for the concatenation product. ⋮ An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic ⋮ Equations and monoid varieties of dot-depth one and two ⋮ On the expressive power of temporal logic for infinite words ⋮ Betweenness of partial orders ⋮ The alphabetic complexity in homomorphic definitions of word, tree and picture languages ⋮ A conjecture on the concatenation product ⋮ Characterizing weighted MSO for trees by branching transitive closure logics ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints ⋮ On a complete set of generators for dot-depth two

Cites Work

This page was built for publication: Classifying regular events in symbolic logic