Results 31 to 40 of about 157,848 (165)
An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects [PDF]
Electronic Proceedings in Theoretical Computer Science, 2015 A zero-one language L is a regular language whose asymptotic probability converges to either zero or one. In this case, we say that L obeys the zero-one law.
Ryoma Sin'ya
doaj +1 more source
Cartesian closed varieties I: the classification theorem [PDF]
Algebra Universalis, 2023 In 1990, Johnstone gave a syntactic characterisation of the equational theories whose associated varieties are cartesian closed. Among such theories are all unary theories—whose models are sets equipped with an action by a monoid M—and all hyperaffine ...
Richard Garner
semanticscholar +1 more source
An Automata Theoretic Characterization of Weighted First-Order Logic [PDF]
Automated Technology for Verification and Analysis, 2023 Since the 1970s with the work of McNaughton, Papert and Sch\"utzenberger, a regular language is known to be definable in the first-order logic if and only if its syntactic monoid is aperiodic.
Dhruv Nevatia, Benjamin Monmege
semanticscholar +1 more source
Logic Meets Algebra: the Case of Regular Languages [PDF]
, 2007 The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e.
Denis Thérien +2 more
core +2 more sources
Syntactic Complexity of R- and J-Trivial Regular Languages [PDF]
, 2013 The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of ...
BAIYU LI +7 more
core +3 more sources
Efficient Aggregation Processing in the Presence of Duplicately Detected Objects in WSNs
Journal of Sensors, Volume 2019, Issue 1, 2019., 2019 Wireless sensor networks (WSNs) have received increasing attention in the past decades. Owing to an enhancement of MEMS technology, various types of sensors such as motion detectors, infrared radiation detectors, ultrasonic sensors (sonar), and magnetometers can detect the objects within a certain range.
Jun-Ki Min +3 more
wiley +1 more source
Languages of Dot-depth One over Infinite Words [PDF]
, 2011 Over finite words, languages of dot-depth one are expressively complete for alternation-free first-order logic. This fragment is also known as the Boolean closure of existential first-order logic.
Kufleitner, Manfred, Lauser, Alexander
core +1 more source
Quantitative Analysis of Software Approximate Correctness
Mathematical Problems in Engineering, Volume 2015, Issue 1, 2015., 2015 Parameterized bisimulation provides an abstract description of software correctness. In real world situations, however, many software products are approximately correct. To characterize the approximate correctness, we generalize the parameterized bisimulation to numerical version and probabilistic setting.
Yanfang Ma, Fabio Tramontana
wiley +1 more source
The Lattice‐Valued Turing Machines and the Lattice‐Valued Type 0 Grammars
Mathematical Problems in Engineering, Volume 2014, Issue 1, 2014., 2014 Purpose. The purpose of this paper is to study a class of the natural languages called the lattice‐valued phrase structure languages, which can be generated by the lattice‐valued type 0 grammars and recognized by the lattice‐valued Turing machines. Design/Methodology/Approach.
Juan Tang +3 more
wiley +1 more source
Counting Closed Orbits for the Dyck Shift
Abstract and Applied Analysis, Volume 2014, Issue 1, 2014., 2014 The prime orbit theorem and Mertens’ theorem are proved for a shift dynamical system of infinite type called the Dyck shift. Different and more direct methods are used in the proof without any complicated theoretical discussion.
Fahad Alsharari +3 more
wiley +1 more source